GATE CSE 2014 Set 3 | Question: 14

Question

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

• A. $O(n^2)$
• B. $O(n \log n)$
• C. $\Theta(n\log n)$
• D. $O(n^3)$

Comments

Whatever is the pivot element the partition algorithm in worst case does not going to divide the array into two parts so in worst case time complexity will be same as first or last element is selected as pivot.

That is O(n^2).

---

1 thing to note why Ans should be n^2 only is If choosing pivot as central element of the array every time reduces quick-sort even some lesser than O(n^2) then we must already had implemented that stratagy of choosing the pivot for quick sort

---

NOTE: Central or middle $\neq$ Median

It may so happen that every time you choose the central element and that central element is either largest or smallest, this is the worst case scenario. Hence, $\Theta (n^2)$ time.

Median = A number which has n/2 elements lesser than or equal to and n/2 elements are greater than or equal to it.

If each time MEDIAN is chosen, then it is the best or avg case of quick sort, so in this case, time complexity will be $\Theta (nlogn)$

See below question:

https://gateoverflow.in/1830/gate-cse-2006-question-52

Answer 1

I think the simplest way to solve this question is if we consider an array of n elements where all the elements are the same since it is not mentioned in the question that the elements need to be distinct. In this case Quick Sort will take $O(n^{2})$ time. Therefore the option will be A.

Answer 2

The tightest upper bound for the worst case performance of quicksort when always choosing the central element of the array as the pivot is O(n^2).

This is because if the input array is already sorted or if the array is sorted in the reverse order and the pivot is always the central element, the partition will always result in one side having n-1 elements and the other side having 0 elements, leading to a worst-case scenario where each partition takes O(n) time and the overall quicksort takes O(n^2) time.

It's important to note that this is an worst-case scenario, and in practice, the average case performance of quicksort is O(n*log(n)) which makes it a good choice for sorting large data sets in most cases.

Also, this worst case is not so likely to happen if the pivot is chosen randomly, rather than always using the central element as pivot.

Answer 3

Option (A)

Taking an Array of 'n' Sorted Elements with Hoare's Partition.

Answer 4

So here, we choose central element as pivot element.

We need to evaluate the worst case performance.

We, know that Quicksort will perform worst when the pivot element is either maximum or minimum.

So, my central element can be maximum or minimum. Central element does not mean the median element.

So my worst case performance would be O($n^{2}$)