Multiple choice

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which the median is selected as pivot?

  1. O(n)

  2. O(n log n)

  3. O(n)3

  4. O(n)2
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

If we use median as a pivot element, then the recurrence for all cases becomes T(n) = 2T(n/2) + O(n) The above recurrence can be solved using Master Method. It falls in case 2 of master method.

Keep practicing — related questions