2939: Complexity Analysis - Revision history

82.132.239.130: Undo revision 409031 by 2001:4450:81E7:1E00:ADD6:A33:300F:1CBB (talk)

2026-03-30T03:33:49Z

Undo revision 409031 by 2001:4450:81E7:1E00:ADD6:A33:300F:1CBB (talk)

2001:4450:81E7:1E00:ADD6:A33:300F:1CBB at 00:38, 30 March 2026

2026-03-30T00:38:29Z

172.69.6.245: Originally this explanation called the runtime asymptotic, which likely stemmed from the common misconception that logarithms are asymptotic as you approach infinity.

2025-05-14T14:38:18Z

Originally this explanation called the runtime asymptotic, which likely stemmed from the common misconception that logarithms are asymptotic as you approach infinity.

172.71.130.66: /* Explanation */

2024-07-01T10:45:06Z

‎Explanation

172.69.43.185: /* Explanation */

2024-06-03T08:13:53Z

‎Explanation

172.69.43.185: /* Explanation */

2024-06-03T08:13:21Z

‎Explanation

172.70.86.35: /* Explanation */

2024-05-31T17:00:55Z

‎Explanation

Asdf: /* Transcript */

2024-05-31T16:46:03Z

‎Transcript

172.69.195.231: /* Explanation */

2024-05-31T16:19:21Z

‎Explanation

Ianrbibtitlht: /* Transcript */ Fix incorrect text contents

2024-05-31T14:59:41Z

‎Transcript: Fix incorrect text contents

@@ Line 8: / Line 8: @@
 | titletext = PERPETUALLY OPTIMISTIC CASE: Early in the execution, our research group makes a breakthrough in proving P=NP.
 }}
-{{TOC}}
 ==Explanation==
 [[Cueball]] is teaching about an algorithm's complexity. The average-case complexity of the algorithm is written in {{w|Big O notation}} as O(''n'' log ''n''), expressing the limiting behavior of the algorithm's runtime as its number of inputs grows larger and larger.

@@ Line 8: / Line 8: @@
 | titletext = PERPETUALLY OPTIMISTIC CASE: Early in the execution, our research group makes a breakthrough in proving P=NP.
 }}
+{{TOC}}
 ==Explanation==
 [[Cueball]] is teaching about an algorithm's complexity. The average-case complexity of the algorithm is written in {{w|Big O notation}} as O(''n'' log ''n''), expressing the limiting behavior of the algorithm's runtime as its number of inputs grows larger and larger.

@@ Line 10: / Line 10: @@
 ==Explanation==
-[[Cueball]] is teaching about an algorithm's complexity. The average-case complexity of the algorithm is written in {{w|Big O notation}} as O(''n'' log ''n''), expressing the asymptotic runtime of the algorithm as the number of inputs to it grows larger and larger.
+[[Cueball]] is teaching about an algorithm's complexity. The average-case complexity of the algorithm is written in {{w|Big O notation}} as O(''n'' log ''n''), expressing the limiting behavior of the algorithm's runtime as its number of inputs grows larger and larger.
 The comic's joke involves taking the terms "best case" and "worst case" far more broadly and literally than intended. Cueball presents not just the best/worst cases for the data input into the function, but also the global environment as a whole, taking in factors such as the United States Congress which should fall ''far'' outside the algorithm's scope.

← Older revision		Revision as of 10:45, 1 July 2024
Line 10:		Line 10:

	==Explanation==		==Explanation==
−	~~{{incomplete\|Created by a PROBABLY DETERMINISTIC 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 complexity of the algorithm is written in {{w\|Big O notation}} as O(''n'' log ''n''), expressing the asymptotic runtime of the algorithm as the number of inputs to it grows larger and larger.		[[Cueball]] is teaching about an algorithm's complexity. The average-case complexity of the algorithm is written in {{w\|Big O notation}} as O(''n'' log ''n''), expressing the asymptotic runtime of the algorithm as the number of inputs to it grows larger and larger.

@@ Line 18: / Line 18: @@
 In particular, the joke regards the analysis of a closed system, which is common in engineering. An algorithm's "best case" is typically its runtime when its inputs have optimal values and it runs in as little time as possible. One example would be a {{w|Sorting algorithm#Comparison of algorithms|sorting algorithm}} that is called with an already-sorted list of numbers; an algorithm ''may'' only need to check each item in the list, in one pass, to confirm this, compared with having to compare an arbitrary number of items against an arbitrary number of others across a number of cycles. The worst case would be when a list is 'unsorted' in a way that presents the maximum number of challenges and actions to the sorting algorithm (possibly, but ''not necessarily'', when presented with the initial list exactly in the wrong order/reversed). These two limits can each be given by an O-notation, but a single O-notation generally indicates the mean complexity of operation encountered for all inputs.
-The joke here is that not only does this algorithm run quicker than what would otherwise be considered its best case scenario, by being terminated early because it is deemed to be 'unnecessary', but its runtime appears to be an hour shorter still because of an act of Congress changing {{w|daylight saving time}}, giving it an end time (in local time) that is an hour less than it would have been under other circumstances. Potentially this would result in an end time that is recorded as earlier than its start time (depending on [[2867: DateTime|how the times are handled]]), and therefore an apparently ''negative'' 'runtime'. Daylight saving time is a [[:Category: Daylight saving time|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 joke here is that not only does this algorithm 'run' quicker than what would otherwise be considered its best case scenario, by being terminated early because it is deemed to be 'unnecessary', but its runtime appears to be an hour shorter still because of an act of Congress changing {{w|daylight saving time}}, giving it an end time (in local time) that is an hour less than it would have been under other circumstances. Potentially this would result in an end time that is recorded as earlier than its start time (depending on [[2867: DateTime|how the times are handled]]), and therefore an apparently ''negative'' 'runtime'. Daylight saving time is a [[:Category: Daylight saving time|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 {{w|Groundhog Day (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|1076: Groundhog Day]].) If the hardware running the algorithm is present in this kind of loop then it may also reset to a previous time before it gets finished, meaning the algorithm would never terminate. This gives rise to a philosophical question about the movie 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 could 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, it would only appear to take as long as it does once the last (non-resetting cycle) leads it into the expected following day.

@@ Line 16: / Line 16: @@
 The comic's joke involves taking the terms "best case" and "worst case" far more broadly and literally than intended. Cueball presents not just the best/worst cases for the data input into the function, but also the global environment as a whole, taking in factors such as the United States Congress which should fall ''far'' outside the algorithm's scope.
-In particular, the joke regards the analysis of a closed system, which is common in engineering. Recently, technology has become so prevalent and integrated with humanity, that conventionally closed systems are now behaving openly. Results regarding external feedback on engineering choices have been emerging on the world stage. People have been engineering more and more for the larger situation possibly using more {{w|Game theory}} than Big O, but continuing to use the analytical approaches that assume systems are closed produces ridiculous results because living beings and societies are now in the loop.
+In particular, the joke regards the analysis of a closed system, which is common in engineering. An algorithm's "best case" is typically its runtime when its inputs have optimal values and it runs in as little time as possible. One example would be a {{w|Sorting algorithm#Comparison of algorithms|sorting algorithm}} that is called with an already-sorted list of numbers; an algorithm ''may'' only need to check each item in the list, in one pass, to confirm this, compared with having to compare an arbitrary number of items against an arbitrary number of others across a number of cycles. The worst case would be when a list is 'unsorted' in a way that presents the maximum number of challenges and actions to the sorting algorithm (possibly, but ''not necessarily'', when presented with the initial list exactly in the wrong order/reversed). These two limits can each be given by an O-notation, but a single O-notation generally indicates the mean complexity of operation encountered for all inputs.
-An algorithm's "best case" is typically its runtime when its inputs have optimal values and it runs in as little time as possible. One example would be a sorting algorithm that is called with an already-sorted list of numbers. 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 {{w|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 [[:Category: Daylight saving time|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 joke here is that not only does this run quicker than the mean O(''n'' log ''n''), being terminated early because it is deemed to be 'unnecessary', but its runtime appears to be an hour shorter still because of an act of Congress changing {{w|daylight saving time}}, giving it an end time (in local time) that is an hour less than it would have been under other circumstances. Potentially this would result in an end time that is recorded as earlier than its start time (depending on [[2867: DateTime|how the times are handled]]), and therefore an apparently ''negative'' 'runtime'. Daylight saving time is a [[:Category: Daylight saving time|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 {{w|Groundhog Day (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|1076: Groundhog Day]].) If the hardware running the algorithm is stuck in this kind of loop that resets to a previous time before it finishes, then the algorithm would never terminate. This gives rise to a philosophical question about the movie 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 could 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, it would only appear to take as long as it did on the final day when it was completed.
+The "worst case" refers to the movie {{w|Groundhog Day (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|1076: Groundhog Day]].) If the hardware running the algorithm is present in this kind of loop then it may also reset to a previous time before it gets finished, meaning the algorithm would never terminate. This gives rise to a philosophical question about the movie 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 could 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, it would only appear to take as long as it does once the last (non-resetting cycle) leads it into the expected following day.
 This may be an indirect reference to the {{w|halting problem}}, a famous problem in computer science. The halting problem is {{w|undecidable}}, meaning that no general algorithm can tell whether a given algorithm will halt, but the widely accepted traditional proof of this relies on external action on details of a system considered closed.
-The title text refers to perhaps an even more famous problem in computer science: {{w|P versus NP problem|P versus NP}}. This asks whether every problem whose solution can be quickly verified (in nondeterministic polynomial time, {{w|NP_(complexity)|NP}}) can also be quickly solved (in polynomial time, {{w|polynomial time|P}}). The P-versus-NP problem is one of the seven {{w|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(''n<sup>k</sup>)''.  However, P vs. NP is a Millennium Prize Problem for a reason; 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 {{w|Optimism bias}} and the {{w|Planning fallacy}}, whereby people tend to assume that the most favourable outcome will be the most likely.
+The title text refers to perhaps an even more famous problem in computer science: {{w|P versus NP problem|P versus NP}}. This asks whether every problem whose solution can be quickly verified (in nondeterministic polynomial time, {{w|NP_(complexity)|NP}}) can also be quickly solved (in polynomial time, {{w|polynomial time|P}}). The P-versus-NP problem is one of the seven {{w|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(''n<sup>k</sup>)''.  However, P vs. NP is a Millennium Prize Problem for a reason; 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 {{w|optimism bias}} and the {{w|planning fallacy}}, whereby people tend to assume that the most favourable outcome will be the most likely.
 ==Transcript==

@@ Line 27: / Line 27: @@
 ==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.]
+:[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.]
 :[Table Heading]

@@ Line 38: / Line 38: @@
 :[Row 2]
 ::Best case
-::The algorithm turns out to be unnecessary and is halted, then Congress enacts surprise daylight saving time and we gain an hour
+::Algorithm turns out to be unnecessary and is halted, then Congress enacts surprise daylight saving time and we gain an hour
 :[Row 3]
 ::Worst case
-::Town in which the hardware is located enters a Groundhog Day scenario, the algorithm never terminates
+::Town in which hardware is located enters a Groundhog Day scenario, algorithm never terminates
 {{comic discussion}}