xkcd

10134 readers

7 users here now

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

founded 2 years ago

MODERATORS

koraro@lemmy.world

126

xkcd #3026: Linear Sort (xkcd.com)

submitted 3 months ago by schnurrito@discuss.tchncs.de to c/xkcd@lemmy.world

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

[–] thevoidzero@lemmy.world 2 points 3 months ago (1 children)

It'd be easier to do 9e5, 8e5 and so on though. Linear decrease in time with each optimization. 1e5.9 seems risky.

[–] Iron_Lynx@lemmy.world 1 points 3 months ago

Depends on how and/or if you want to curve future changes. Going 1e5.9, 1e5.8, 1e5.7, ... will curve logarithmically, while 9e5, 8e5, 7e5, ... will curve linearly within each power of ten, then get a discontinuity at 1e5 and go 9e4 and scale linearly at a different rate.

Of course, you'll have to be an absolute nerd to find that a problem and there's a nonzero chance that I'm such a nerd and I just admitted my guilt 😅