schnurrito@discuss.tchncs.de to xkcd@lemmy.worldEnglish · 9 days agoxkcd #3026: Linear Sortxkcd.comexternal-linkmessage-square12fedilinkarrow-up1123arrow-down10file-text
arrow-up1123arrow-down1external-linkxkcd #3026: Linear Sortxkcd.comschnurrito@discuss.tchncs.de to xkcd@lemmy.worldEnglish · 9 days agomessage-square12fedilinkfile-text
minus-squareNeatNit@discuss.tchncs.delinkfedilinkEnglisharrow-up11arrow-down1·edit-28 days agoReally 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!
minus-squareGustephan@lemmy.worldlinkfedilinkEnglisharrow-up5arrow-down1·7 days agoYou should know better too! Behaviour at large n is irrelevant to “best case” complexity analysis of sorting algorithms
minus-squareNeatNit@discuss.tchncs.delinkfedilinkEnglisharrow-up2·6 days agoOf course it still matters, you just take the best case for n as n→∞, instead of the worst or average case.
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!
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.