explain xkcd - User contributions [en]

3026: Linear Sort

2024-12-19T07:22:53Z

172.69.23.12: /* Explanation */ all comparison sorting algorithms are Omega(n log n). Saying the best ones are O(n log n) doesn’t mean anything because any O(n) algorithm is also O(n log n)

{{comic
| number = 3026
| date = December 18, 2024
| title = Linear Sort
| image = linear_sort_2x.png
| imagesize = 385x181px
| noexpand = true
| titletext = The best case is O(n), and the worst case is that someone checks why.
}}

==Explanation==
{{incomplete|Created in Θ(N) TIME by an iterative Insertion Sorter working on a multidimensional array - Please change this comment when editing this page. Do NOT delete this tag too soon.}}
A common task in programming is to sort a list, a list being a collection of related elements of data that are stored in a linear fashion. There are dozens of algorithms that have been created for this through the years, from simple to complex, and each has its own merits with regards to how easy it is to understand / implement, how much space it uses, and how efficiently it operates on the data.

In computer science, the runtime of an algorithm can be described using {{w|Big O Notation}}, which categories the asymptotic, usually average, runtime (''O'') of a function of the number of elements (''n'') operated on (''f(n)'') as it grows larger and larger towards infinity; this creates the form O(''f''(''n'')) as the final description. Being asymptotic means that Big O Notation only considers parts of the function that scale with time and disregards fixed changes such as multipliers and additions to the scaling time. For instance, in an O(''n'') algorithm, ''f''(''n'') is simply ''n'', meaning it takes a constant amount of time per element operated on. A simple example would be examining pictures: if it takes one second to look at a picture, it would take ten seconds to look at ten pictures; if it took three seconds to look at a picture, it would take thirty seconds to look at ten pictures - both are described as O(''n'').

Generally, programmers seek to minimize the Big O Notation of their algorithms because it means they take less time. It can be proven that all general-purpose sorting methods are Ω(''n'' log ''n''); since this is larger than ''n'' on its own, it means that algorithms will always begin to take longer per element as the number of elements increases.

Here are some examples of common runtimes expressed in Big O notation, from smallest to largest:
<ul><li>O(1) - Constant time, which means the execution time is independent of the size of the data</li>
<li>O(''n'') - Linear time, which means the execution time grows in direct proportion to the size of the data</li>
<li>O(''n'' log(''n'')) - The execution time grows proportionally to ''n'' * the {{w|logarithm}} of ''n'', with the added ''log(n)'' creating an increasingly larger multiplier on the runtime</li>
<li>O(''n''2) - Quadratic time, meaning the execution time grows proportionally to the ''square'' of the size of the data.</li></ul>

The code in the comic describes a 'linear' sort that first sorts the list using {{w|merge sort}}, which is known to take time O(''n'' log(''n'')), and then `sleep()`s (pauses with no activity) for a complimentary amount of time by subtracting the time taken for the sort from the number of elements multiplied by 1 million (1e6) seconds. This way, the total time always scales proportionately with the number of elements. This effectively converts the algorithm, through brute force, to fit the definition of linear time: it takes one million seconds — which is more than 11 days — per element, rather than a non-linear progression as the number of elements increases. Although this algorithm ''does'' run in O(''n''), it does not reflect that it is made to be significantly slower than the nominally 'worse' O(''n'' log(''n'')) performance that the embedded sort takes by itself.

It should be noted that for sufficiently large lists, the merge sort will take longer than the million seconds per element, which results in a negative value being passed to the sleep() function. This might halt the program with a runtime error, produce {{w|Integer overflow#Definition variations and ambiguity|unpredictably extra-long}} additional waits or skip any additional wait; all of these still leaving the issue of already having exceeded O(''n''). However, this issue will only arise for impossibly huge lists: if, for instance, a merge sort took ''n log(n)'' microseconds to complete (which would be considered slow, by today's typical processing times), then the comic's 'linear' sort target would be reached sooner only for lists longer than 21,000,000,000,000 ≈ 10300,000,000,000 elements — a number far larger than the number of atoms in the universe. The practical impossibility of this outcome might be why such a ridiculously high number of seconds was chosen.

The title text refers to the {{w|Best, worst and average case|best and worst case}} of a sort, which are additional measures of its runtime to describe the shortest and longest potential times. A more optimal sort may decide how much of a list needs to be passed over again after its first pass of shuffling elements around; scanning a pre-sorted list (and deducing that it has no more checking to do) could mean that no more effort is needed, resulting in a best case of O(''n''). Depending upon the algorithm, presenting a list that is in an ordering that happens to challenge it the most (such as exactly reversed) may mean even an 'average O(''n'' log ''n'')' process would have to exceed this, resulting in a worst-case number of operations that may be O(''n2''). It can be very useful to know that a given sorting method ''may'' take the average order of time, but have the possibility of a much shorter ''or'' longer runtime... especially when the method is expected to be [[1185: Ineffective Sorts|far, far worse than others]], where only particular and more idealistic input lets it approach the more satisfyingly fast average/best responses.

By forcing all practical searches to take O(''n'') time, regardless of how otherwise identical data is presorted, the best case (and worst case, for that matter) will also be O(''n''). The last part of the text then plays on another meaning of best case and worst case, as best- and {{w|worst-case scenario}}s for a situation, by saying that the worst outcome for the code's author is when someone decides to investigate the code (perhaps owing to its absurd runtime, or else just justifiably skeptical of the declared optimality), whereupon that investigator will discover the deception and ruin the author's reputation.

==Transcript==
{{incomplete transcript|Do NOT delete this tag too soon.}}
:[The panel shows five lines of code:]
:function LinearSort(list):
::StartTime=Time()
::MergeSort(list)
::Sleep(1e6*length(list)-(Time()-StartTime))
::return

:[Caption below the panel:]
:How to sort a list in linear time

{{comic discussion}}

[[Category:Programming]]

2957: A Crossword Puzzle

2024-07-10T21:14:06Z

172.69.23.12: /* Explanation */ Populated 29 down

{{comic
| number = 2957
| date = July 10, 2024
| title = A Crossword Puzzle
| image = a_crossword_puzzle_2x.png
| imagesize = 740x937px
| noexpand = true
| titletext = Hint: If you ever encounter this puzzle in a crossword app, just [term for someone with a competitive and high-achieving personality].
}}

==Explanation==
{{incomplete|CreAAAAAAAAted by AAAAAAAAAA BOT - Please change this comment when editing this page. Do NOT delete this tag too soon.}}

* 1 across. Famous pvt. wilhelm quote: Reference to the {{w|Wilhelm scream}}.
* 11 across. An IPv4 record is an "A" record, an IPv6 record is four times the length and is designated an "AAAA" record.
* 17 across. The {{w|A-10 Warthog}} is a well-known attack aircraft. Here, A-10 has been turned into AAAAAAAAAA (ten As).
* 18 across. Aphantasia is the inability to visualize. Following the instruction, we determine that '''A'''ph'''a'''nt'''a'''si'''a''' gives us the word "aaaa".
* 22 across. Unary's when you get to use just the one symbol. E.g. 32 in unary would be 11111111111111111111111111111111. The first four strings in unary, if you used A as the first (and only) symbol, would be A, AA, AAA, AAAA.
* 29 across. A reference to Howard Dean, an American Democrat who ran for the party's nomination in 2004. He famously [https://www.youtube.com/watch?v=l6i-gYRAwM0 yelled at a rally] in a way that was thought to be bizarre and which, it is thought, doomed his campaign.
* 36 across. I.e. "open up". Or an expression of pain; particularly the only kind you can make with dental tools in your mouth. (As Autechre put it: [https://youtu.be/UppsLKz1iD4 "Now, I don't want you to panic... just lean back and relax."])
* 41 across. Macaulay Culkin's review of aftershave: Famously in the movie {{w|Home Alone}} he puts it on because he's home all alone and dislikes it, emitting a scream, which could be transcribed like A's.
* 50 across. The call which Elsa hears in Frozen 2 is a sequence of four notes which resemble the Dies Irae. The sequence is sung entirely with an open rounded vowel sound, or a soft "a" sound.
* 1 down. {{w|AaAaAA!!! – A Reckless Disregard for Gravity}} - notably the title is commonly extended in promotional material beyond 6 A's.
* 2 down. 10101010 10101010 10101010 in binary is equivalent to "AAAAAA" in hexadecimal.
* 3 down. the Pixel 6a was released in July 22. Stylized in this puzzle as "AAAAAA"
* 26 down. A high budget video game is usually referred to as A Triple-A game, or AAA
* 29 down. `echo -n AAAAAAAA | sha256sum` outputs `c34ab6abb7b2bb595bc25c3b388c872fd1d575819a8f55cc689510285e212385`.
* 34 down. 440Hz is an "A" note. 7 pulses would be AAAAAAA
* 39 down. A [https://en.wikipedia.org/wiki/Multi-tap "multitap keyboard"] is a text entry system for mobile phones. Most numbers are associated with three letters, and tapping the same number multiple times in rapid succession selects the 1st, 2nd, or 3rd number. 2 is "a", 22 is "b", 222 is "c", 3 is "d", etc. 2-2-2-2-2-2 translates to "aaaaaa"
* 40 down. .- is Morse Code for A. It reads out as AAAAAA
* Hint: If you ever encounter this puzzle in a crossword app, just [ Type A ]

==Transcript==
{{incomplete transcript|Do NOT delete this tag too soon.}}

[A crossword puzzle image, with the following clues:]

:Across
:1. Famous Pvt. Wilhelm quote
:11. IPv6 address record
:15. "CIPHERTEXT" decrypted with Vigenere key "CIPHERTEXT"
:16. 8mm diameter battery
:17. "Warthog" attack aircraft
:18. Every third letter in the word for "inability to visualize"
:19. An acrostic hidden on the first page of the dictionary
:21. Default paper size in Europe
:22. First four unary strings
:23. Lysine codon
:24. 40 CFR part 63 subpart concerning asphalt pollution
:25. Top bond credit rating
:26. Audi coupe
:27. A pair of small remote batteries, when inserted
:29. Unofficial Howard Dean slogan
:32. A 4.0 report card
:33. The "Harlem Globetrotters of baseball" (vowels only)
:32. 2018 Kiefer song
:35. Top Minor League tier
:35. Reply elicited by a dentist
:38. ANAA's airport
:41. Macaulay Culkin's review of aftershave
:43. Marketing agency trade grp.
:44. Soaring climax of Linda Elder's ''Man of La Mancha''
:46. Military flight commuinity org.
:47. Iconic line from Tarzan
:48. Every other letter of Jimmy Wales's birth state
:49. Warthog'd postscript after "They call me ''mister'' pig!"
:50. Message to Elsa in ''Frozen 2''
:51. Lola, when betting it all on Black 20 in ''Run Lola Run''
:Down
:1. Game featuring "a reckless disregard for gravity"
:2. 101010101010101010101010 base 2-> base 16
:3. Google phone released July '22
:4. It's five times better than that ''other'' steak sauce
:5. ToHex(43690)
:6. Freddie Mercury lyric from ''Under Pressure''
:7. Full-size Audi luxury sedan
:8. Fast path through a multiple choice marketing survey
:9. 12356631 in base 26
:10. Viral Jimmy Barnes chorus
:11. Ruby Rhod catchphrase
:12. badbeef + 9efcebbb
:13. In Wet Let's ''Ur Mum'', what the singer has been practicing
:14. Refrain from Nora Reed bot
:20. Mario button presses to ascend Minas Tirith's walls
:24. Vermont historic route north from Bennington
:26. High-budget video game
:28. Unotrhodox Tic-Tac-Toe win
:29. String whose SHA-256 hash ends "...689510285e212385"
:30. Arnold's remark to the Predator
:31. The vowels in the fire salamander's binomial name
:32. Janet Leigh ''Psycho'' line
:34. Seven 440Hz pulses
:37. Audi luxury sports sedan
:38. A half-dozen eggs with reasonably firm yolks
:39. 2-2-2-2-2-2 on a multitap phone keypad
:40. .- .- .- .- .- .-
:42. Rating for China's best tourist attractions
:43. Standard drumstick size
:45. "The rain/in Spain/falls main-/ly on the plain" rhyme scheme

{{comic discussion}}