algorithmtime-complexitybig-oquicksort

Worst case runtime of random quicksort if you keep randomly choosing a pivot and partitioning until you find a good pivot


If you changed the random quicksort algorithm to repeatedly randomly pick a pivot and run partition until it finds a "good" pivot what would be the worst case cost of the algorithm? If we kept track of the pivots used so far so that we never use the same one twice for the same array.


Solution

  • In the worst case, the random pivot always is the maximum or minimum possible value, in which case the runtime is O(n^2). For a more detailed analysis, look here. The expected value of the runtime is still O(n * log n) though.