7mo ago

xkcd #3026: Linear Sort

Linear Sort

The best case is O(n), and the worst case is that someone checks why.

12 comments

Really annoys me that this is actually O(n log n) because for large enough n the merge sort will take longer than n1e6 second. Randall should know better!
- You should know better too! Behaviour at large n is irrelevant to "best case" complexity analysis of sorting algorithms
  
  Of course it still matters, you just take the best case for n as n→∞, instead of the worst or average case.
And if anyone asks you optimise the function, just mess with the sleep function!
- Sleep(1e5.9[...]), where [...] is everything else, and hope that the compiler or interpreter can handle non-integer exponents for this type of scientific notation.
  
  It'd be easier to do 9e5, 8e5 and so on though. Linear decrease in time with each optimization. 1e5.9 seems risky.
They need to fix their mobile website. It has large side margins for no reason, and the comic is tiny. I have to zoom in every time I visit to read the comic. Makes no sense.
- There is m.xkcd.com but I don't link to that when I post here, only use it to copy the title text.
  
  In this day and age, the regular site should serve a mobile-friendly page on a phone. There is CSS to detect the browser size and orientation and change the style.

12 comments