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