edited by
30,658 views
61 votes
61 votes

You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

  1. $O(n^2)$
  2. $O(n \log n)$
  3. $\Theta(n\log n)$
  4. $O(n^3)$
edited by

10 Answers

Best answer
107 votes
107 votes

Correct Option: A – $O(n^2)$.

When we choose the first element as the pivot, the worst case of quick sort comes if the input is sorted- either in ascending or descending order. Now, when we choose the middle element as pivot, sorted input no longer gives worst case behavior. But, there will be some permutation of the input numbers which will be giving the same worst case behavior. For example,

$1 \ 2 \ 3 \ 4 \ 5   \ 6  \ 7$
This array gives worst case behavior for quick sort when the first element is pivot.

$6 \ 4 \ 2 \ 1 \ 3 \ 5 \ 7$
This array gives the worst case behavior of $O(n^2) $ if we take middle element as the pivot- each split will be $1$ element on one side and $n-1$ elements on other side. Similarly, for any input, we can have a permutation where the behavior is like this. So, whichever element we take as pivot it gives worst case complexity of $O(n^2)$ as long as pivot is from a fixed position (not random position as in randomized quick sort).

edited by
13 votes
13 votes

You already know that when choosing the first or last element as pivot, quick sort gives worst case complexity in ascending/descending order. It also gives worst case O(n2) when all elements are same.

Simply, check for all these cases first.

So, in ascending/descending order, choosing mid element as pivot gives O(nlogn) but choosing all elements same such as [2 2 2 2 2] still gives O(n2).

 

1 votes
1 votes
A.

The Worst case time complexity of quick sort is O (n^2). This will happen when the elements
of the input array are already in order (ascending or descending), irrespective of position of
pivot element in array.
1 votes
1 votes
when we select the central element as pivot element then the worst case time complexity will be O(nlogn).You may get doubt why not always choose mid element as pivot,this is because although this produceses O(nlogn) time complexity when we compute the constant time also then this will be more than selecting other elements as pivot.
Answer:

Related questions

37 votes
37 votes
11 answers
4