### Find the minimum element of an array using Randomized Select sorting quicksort randomizedselection timecomplexity array    Posted: 6 years ago Edit answers (1) views (4048)

What would be the worst case running time to find the minimum element of an array using Randomized Select?

 Posted: 6 years ago Updated: 6 years ago 0 0 Edit 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.Suppose we have an array [3, 2, 9, 0, 7, 5, 4, 8, 6, 1] . The Randomized Select will select [9,8,7,6,5,...1] such that the partition in the worst case is Select 9 : partition into [3, 2, 0, 7, 5, 4, 8, 6, 1] and 9 Select 8 : partition the first set in 1) into [3, 2, 0, 7, 5, 4, 6, 1] and 8 $$\vdots$$ Select 1 : partition the first set in 9) into 0 and 1 . Worst case running time = $$O(n^{2})$$.