Main Page
Welcome to the explain xkcd wiki! We already have 12 comic explanations!
(But there are still 2927 to go. Come and add yours!)
Latest comic
| Complexity Analysis |
 Title text: PERPETUALLY OPTIMISTIC CASE: Early in the execution, our research group makes a breakthrough on proving P=NP. |
Explanation
|
This explanation may be incomplete or incorrect: Created by a PERPETUALLY OPTIMISTIC BOT - Please change this comment when editing this page. Do NOT delete this tag too soon. |
Cueball is teaching about an algorithm's complexity. The average-case runtime of the algorithm is written as O(n log n), in Big O notation, expressing the asymptotic runtime of the algorithm as the number of inputs to it grows larger and larger. This is an error by Randall (or Cueball), as Big-O notation represents only the worst-case, not average-case time complexity.
The "best case" for an algorithm is typically its runtime when its inputs have optimal values and it runs in as little time as possible. The joke here is that not only does it run quicker than this by being terminated early because it's 'unnecessary', but its runtime appears to be an hour shorter still because of an act of Congress changing daylight saving time, giving it an end time (in local time) that is an hour less than it would otherwise have been. Potentially this would result in an end time that is less than its start time, and therefore an apparently negative 'runtime'. Daylight saving time is a recurrent theme on xkcd, and it is clear that Randall is not a fan, so Congress making surprise DST changes is another way for Randall to mock the concept.
The "worst case" refers to the movie Groundhog Day, in which the same events occur over and over in a sort of time loop. (This movie has been referenced before in 1076: Groundhog Day.) If the hardware running the algorithm is stuck in this kind of loop that resets to a previous time before it ever gets finished, then the algorithm would never terminate. This gives rise to a philosophical question as to whether the whole world is reset after every day, or just the town where the movie takes place. If it is just the town, and you can still connect to their hardware from outside, then from that perspective the algorithm would appear to be taking an interminably long time to run. If the whole world resets, since people (aside from the movie's main character) do not experience the reset of the day, it would only appear to take as long as it did on the final day when it successfully completed.
This may be an indirect reference to the halting problem, a famous problem in computer science. The halting problem is undecidable, meaning that there is no general algorithm that can tell whether a given algorithm will halt.
The title text refers to perhaps an even more famous problem in computer science: P versus NP. This asks whether every problem whose solution can be quickly verified (in nondeterministic polynomial time, NP) can also be quickly solved (in polynomial time, P). The P-versus-NP problem is one of the seven Millennium Prize Problems, and as such has a $1 million prize for its solution. Presumably, the problem discussed here is in NP, so if P=NP, its worst-case runtime would be some polynomial O(nk). However, P vs. NP is a Millennium Prize Problem for a reason, and most computer scientists expect that P != NP, so hoping for a breakthrough in proving P=NP is "perpetually optimistic". This may be a reference to Optimism bias and the Planning fallacy, whereby people tend to assume that the most favourable outcome will be the most likely.
Transcript
- [Cueball is holding a presentation pointer stick, pointing to a table behind him that towers above him. The table has a heading above it and then two columns and three rows. the first column is slim and the second much broader.]
- Results of algorithm complexity analysis:
Average case O(n log n) Best case Algorithm turns out to be unnecessary and is halted, then Congress enacts surprise daylight saving time and we gain an hour Worst case Town in which hardware is located enters a Groundhog Day scenario, algorithm never terminates
New here?
Feel free to sign up for an account and contribute to the explain xkcd wiki! We need explanations for comics, characters, themes, memes and everything in between. If it is referenced in an xkcd web comic, it should be here.
- If you're new to wikis like this, take a look at these help pages describing how to navigate the wiki, and how to edit pages.
- Discussion about various parts of the wiki is going on at Explain XKCD:Community portal. Share your 2¢!
- List of all comics contains a complete table of all xkcd comics so far and the corresponding explanations. The red links (like this) are missing explanations. Feel free to help out by creating them!
Rules
Don't be a jerk. There are a lot of comics that don't have set in stone explanations, feel free to put multiple interpretations in the wiki page for each comic.
If you want to talk about a specific comic, use its discussion page.
Please only submit material directly related to—and helping everyone better understand—xkcd... and of course only submit material that can legally be posted (and freely edited.) Off-topic or other inappropriate content is subject to removal or modification at admin discretion, and users posting such are at risk of being blocked.
If you need assistance from an admin, feel free to leave a message on their personal discussion page. The list of admins is here.
Logo
Explain xkcd logo courtesy of User:Alek2407.
