I need to show that a random pivot quick sort algorithm can be made to run O(nlogn) in the worst case. Not sure how to do this, since worst case (in my understanding) occurs when the pivot is selected to be the lowest value, resulting in a running time of O(n^2).
Here is the recurrence that I am using: T(n) = T(n-1) + T(1) + an
I'm thinking that I may be going about this wrong because I am not necessarily considering a truly random pivot...but rather assuming that the lowest value is randomly selected as the pivot.
Help, please!