737

submitted 1 week ago by cm0002@lemmy.world to c/programmer_humor@programming.dev

42 comments fedilink hide all child comments

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

[-] magic_lobster_party@fedia.io 7 points 1 week ago

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).