2939: Complexity Analysis

Complexity Analysis

|< < Prev #2939 (May 29, 2024) Next > >|

Title text: PERPETUALLY OPTIMISTIC CASE: Early in the execution, our research group makes a breakthrough on proving P=NP.

|< < Prev Random Explanation Next > >|

Explanation

This is one of 52 incomplete explanations: Created by a PERPETUALLY OPTIMISTIC BOT - Please change this comment when editing this page. Do NOT delete this tag too soon. If you can fix this issue, edit the page!

Transcript

This is one of 27 incomplete transcripts: Do NOT delete this tag too soon. If you can fix this issue, edit the page!

[Cueball is holding a presentation pointer stick, pointing to a table behind him]

[Title above the table:]

Results of algorithm complexity analysis:

[Table content:]

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

  Add comment        Create topic (use sparingly)       Refresh 

Discussion

I could be mistaken, but I think the "Best case" doesn't actually describe a situation where the algorithm takes the minimum amount of time. Rather, it describes that the algorithm wasn't necessary in the first place, possibly due to something like the list incidentally already being sorted. 172.68.23.74 23:25, 29 May 2024 (UTC)

If you want to check that it's sorted, then you need to traverse the entire list at least once (worst case is that the list is in fact sorted and you need to run through the whole thing) O(n). The best case example would be like checking for orderliness and finding the first two items out of order and quitting. THEN congress enacts the time shift and you could have taken some "negative" amount of time to run that "check_if_sorted" routine. 172.69.71.134 14:36, 30 May 2024 (UTC)

I think the joke is that someone externally decides that the algorithm is redundant, and so terminates it before completion (or never runs it at all).172.70.162.185 17:05, 30 May 2024 (UTC)

I think, in the best case scenario the Congress would need to make a surprise revert of Daylight Saving Time to really gain an hour. As during Daylight Saving the clock is set into the future it still would be virtually one hour later if suddenly Daylight Saving starts. But if it stops suddendly, you gain one hour on the clock. 162.158.94.238 05:56, 30 May 2024 (UTC)

Sounds like a matter of conventional definition among those familiar with Deep Algorithm Magicks. As a mere initiate, I'd say that defining an algorithm's performance in terms of factors outside the algorithm's context, such as the possibility that it might not need to run at all, brings in a host of reference problems that I'd rather not take up arms against.162.158.41.121 06:14, 30 May 2024 (UTC)

I'd say using Big-O for the average case if a very bad one exists is NOT an abuse. Big-O in first place defines the behavior of a *function*, not a set of functions. Thus, I wouldn't have the slightest problems if a publication writes, say, "Algorithm A takes O(n) steps if x!=y, but unfortunately, O(n^n) steps if x=y, which happens very rarely..." 172.71.160.70 07:35, 30 May 2024 (UTC)

I think the table in the Transcript section that reproduces the table from the comic should be moved to the Explanation section and rewritten in paragraph form in the Transcript section. We only include text within the Transcript section to help vision-impaired readers. Ianrbibtitlht (talk) 12:40, 30 May 2024 (UTC)

It should be re-written for the transcript. I'm not convinced that reproducing it in the explanation would add anything of value to that though.172.69.195.5 12:46, 30 May 2024 (UTC)

You're not wrong! Ianrbibtitlht (talk) 13:10, 30 May 2024 (UTC)

"[...] conventionally closed systems are now behaving in open manners [...]" - unless this is a badly phrased way of saying something like "real-world engineering is always more complicated than a simple technical analysis would suggest", I think these parts of the explanation are going way off base. 172.70.162.186 19:02, 30 May 2024 (UTC)

Interesting he‘s not using theta(…) and Omega(…) but O(…) only. -- Grimaldi (talk) 20:03, 24 June 2024 (please sign your comments with ~~~~)
        Add comment