this post was submitted on 08 Apr 2025
731 points (98.4% liked)
Programmer Humor
22809 readers
738 users here now
Welcome to Programmer Humor!
This is a place where you can post jokes, memes, humor, etc. related to programming!
For sharing awful code theres also Programming Horror.
Rules
- Keep content in english
- No advertisements
- Posts must be related to programming or programmer topics
founded 2 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
Maybe it’s like teaching kids the quadratic equation; where it’s less about learning the thing and more about understanding how to problem solve and use logic.
In this case maybe the point is to show an understanding of algorithms and that you can explain them out loud.
The quadratic equation is the basis for most other math and physics. It’s used all the time.
The good thing about quicksort is that it’s a good demonstration of an O(n log n) algorithm, and that’s about it.
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
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).
That's when you add a w.h.p. (with high probability)