Worst Case Complexity of Randomized Quicksort

Introduction:
Randomized Quicksort is an algorithm that is an extension of the original Quicksort algorithm. In Quicksort, the pivot element is chosen deterministically, usually as the last element of the array. However, in Randomized Quicksort, the pivot element is chosen randomly from the array. This random selection helps to avoid the worst-case scenarios that can occur in Quicksort.

Worst Case Complexity:
The worst-case complexity of sorting n numbers using Randomized Quicksort is O(n^2). This means that in the worst-case scenario, the time complexity of the algorithm grows quadratically with the size of the input.

Explanation:
The worst-case complexity occurs when the pivot element always turns out to be the smallest or the largest element in the array. This causes the array to be partitioned in a highly unbalanced manner, with one partition containing all the elements except the pivot. In such cases, the algorithm performs poorly and takes a long time to sort the array.

To understand this, let's consider an example where the array is already sorted in ascending order. If the first element is chosen as the pivot, the partitioning will result in one partition with n-1 elements and another partition with no elements. In this case, the time complexity of the algorithm becomes O(n^2).

In the worst-case scenario, the partitioning process divides the array into two sub-arrays of size 0 and n-1. This happens when the pivot element is either the smallest or the largest element in the array. In each recursive step, the size of the sub-array reduces by only 1, resulting in a total of n recursive steps. Since each step takes O(n) time for partitioning, the overall time complexity becomes O(n^2).

Conclusion:
In conclusion, the worst-case complexity of sorting n numbers using Randomized Quicksort is O(n^2). This worst-case scenario occurs when the pivot element is always the smallest or the largest element in the array, causing highly unbalanced partitioning. However, on average, Randomized Quicksort performs much better than the worst-case complexity and has an expected time complexity of O(n log n).