# Why does Randomized Quicksort have O(n log n) worst-case runtime cost

Randomized Quick Sort is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $$O(n^2)$$, as the worst case happens when randomly chosen pivot is selected in sorted or reverse sorted order. But in some texts [1] [2] its worst case time complexity is written as $$O(n\log{n})$$

What's correct?

• You should this "some text" you are talking about. There is something hidden there. You will find it if you read again this "text" – AJed Jan 6 '15 at 3:25
• Note: Link [1] is dead. Link [2] clearly states that the algorithm is randomized, so for any input you don't have "a runtime", but "an expected runtime". And the expected runtime for the worst possible input is O (n log n). – gnasher729 May 7 '19 at 22:23

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.

• So in general we can say it behaves as quadratic in worst case – Atinesh Jan 6 '15 at 5:47
• @Atinesh No, at least if you mean $\Theta$ by that. – Raphael Jan 6 '15 at 8:40
• I think it's correct to say the worst-case performance of randomized quicksort is $O(n^2).$ – James Evans Jan 6 '15 at 14:54
• Quicksort may take only $\Theta(n\log n)$ time in worst case if one employs a linear-time algorithm to find the median as the pivot. Of course, randomized quicksort has a better practical performance usually. – Bangye Jan 6 '15 at 19:04

You were missing that these texts talk about "worst case expected run time", not "worst case runtime".

They are discussing a Quicksort implementation that involves a random element. Normally you have a deterministic algorithm, that is an algorithm which for a given input will always produce the exact same steps. To determine the "worst case runtime", you examine all possible inputs, and pick the one that produces the worst runtime.

But here we have a random factor. Given some input, the algorithm will not always do the same steps because some randomness is involved. Instead of having a runtime for each fixed input, we have an "expected runtime" - we check each possible value of the random decisions and their probability, and the "expected runtime" is the weighted average of the runtime for each combination of random decisions, but still for a fixed input.

So we calculate the "expected runtime" for each possible input, and to get the "worst case expected runtime", we find the one possible input where the expected runtime is worst. And apparently they showed that the worst case for the "expected runtime" is just O (n log n). I wouldn't be surprised if just picking the first pivot at random would change the worst case expected runtime to o (n^2) (little o instead of Big O), because only a few out of n pivots will lead to worst case behaviour.

Note that there are two things to take expectation/average over: the input permutation and the pivots (one per partitioning).

For some inputs and implementations of Quicksort all pivots are bad ($n$ times the same number sometimes works) so randomisation does not help. In such a case the expected time (averaging over pivot choices) can be quadratic in the worst case (a bad input). Still, the "overall" expected time (averaging over both inputs and pivot choices) is still $\Theta(n \log n)$ for reasonable implementations.

Other implementations have true worst-case runtime in $\Theta(n \log n)$, namely those that pick the exact median as pivot and deal with duplicates in a nice way.

Bottom line, check your source(s) for which implementation they use and which quantity they consider random resp. fixed in their analysis.

• Consider this question postimg.org/image/fiurc4z87 that I've asked in exam. What appropriate ans would you suggest I think (c) – Atinesh Jan 6 '15 at 10:49
• @Atinesh I think my answer provides you with enough information on this. – Raphael Jan 6 '15 at 13:08

Yes you are corect, it will be $O(n^2)$.

The worst case for randomized quicksort is same elements as input. Ex: 2,2,2,2,2,2

Here the algorithm whatever it picks will be $T(n) = T(n-1) + n$ and hence $O(n^2)$.

• That's if you have an exceedingly daft implementation of quicksort. Any decent implementation will in the first partition exchange #1 and #6, #2 and #5, #3 and #4, and will then sort two subarrays of length 3. – gnasher729 Dec 10 '16 at 21:54
• I guess you have <= as well as >= on both the pointers that scans from LHS and RHS. That's why you are saying so. '=' is associated with either of the pointers, not both. In that case the recursion tree grows till n. – lu5er Dec 20 '16 at 8:20
• And that's what I call an exceedingly daft implementation. Any implementation that takes quadratic runtime for the case "all elements are equal" is criminally stupid. There are actually implementations that take linear time in this case (O (n), not O (n log n)). – gnasher729 May 7 '19 at 22:18