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