Question

Randomized quick sort is one where pivot is choosen randomly. The time complexity recurrence for the worst case scenario of randomized quick sort is

• A. $T\left(n\right)=T(n-1)+n$
• B. $T\left(n\right)=T(n-1)+1$
• C. $T\left(n\right)=2T(n-2)+n$
• D. $T\left(n\right)=2T\left(n/2\right)+n$

Answer 1

The correct option is A $T\left(n\right)=T(n-1)+n$

In Randomized Quick sort also the pivot can get fixed up at extreme postions of the array.