If I’m not mistaken, quick sort is worst case O(n^2), merge sort is what actually achieves O(nlogn), the point is that quicksort is on average more memory (and time?) efficient

[–] magic_lobster_party@fedia.io 7 points 10 months ago (1 children)

Maybe.

When using a random pivot, the worst case becomes exponentially more unlikely the larger the n. The O notation only cares about the complexity when n approaches infinity. So when n approaches infinity, the likelihood of O(n^2) performance approaches 0 (and the likelihood of O(n log n) approaches 1).

I think it’s fine to call it O(n log n).

[–] MBM@lemmings.world 4 points 10 months ago

That's when you add a w.h.p. (with high probability)

[–] captain_aggravated@sh.itjust.works 11 points 10 months ago

"The basis for most other math and physics" they do a complete fucksewage job at demonstrating that in school. I remember several years in math class "And here's the quadratic equation, the one that's all over 2a" and it was an exercise in plugging and chugging.

Math is a useful, powerful and allegedly beautiful thing. it's such a shame it's illegal to teach it competently.