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

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


Posted Answers

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


  1. Select 9 : partition into [3, 2, 0, 7, 5, 4, 8, 6, 1] and 9
  2. Select 8 : partition the first set in 1) into [3, 2, 0, 7, 5, 4, 6, 1] and 8
    \( \vdots \)
  3. Select 1 : partition the first set in 9) into 0 and 1 .


Worst case running time = \( O(n^{2}) \).

You need to Sign In to post your solution.