xkcd

9048 readers

142 users here now

A community for a webcomic of romance, sarcasm, math, and language.

founded 2 years ago

MODERATORS

koraro

123

xkcd #3026: Linear Sort (xkcd.com)

submitted 3 weeks ago by [email protected] to c/xkcd

12 comments fedilink hide all child comments

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

https://explainxkcd.com/3026/

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 10 points 3 weeks ago* (last edited 3 weeks ago) (1 children)

Really annoys me that this is actually O(n log n) because for large enough n the merge sort will take longer than n*1e6 second. Randall should know better!

[–] Gustephan 4 points 3 weeks ago (1 children)

You should know better too! Behaviour at large n is irrelevant to "best case" complexity analysis of sorting algorithms

[–] [email protected] 2 points 2 weeks ago

Of course it still matters, you just take the best case for n as n→∞, instead of the worst or average case.