What would be the worst case running time to find the minimum element of an array using Randomized Select?
In the worst case, Randomized Select will make the partition by picking the maximum element. The partition will create (n-1) elements in one set and 1 element in the other.
Worst case running time = \( O(n^{2}) \). |