GATE CS 2014 Set 3 Q.24 (CS Q.14): Searching and Sorting Algorithms

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

$O(n^2)$

$O(n \log n)$

$\Theta(n \log n)$

$O(n^3)$

Official answer and solution

Official answer: A
From: Official GATE 2014 answer key

Solution

Analyze the worst-case performance of quicksort with deterministic pivot selection.

In quicksort, if the pivot selection strategy is deterministic (such as choosing the first, last, or central element at index $\lfloor n/2 \rfloor$ ):
There exist permutations of input elements for which the chosen pivot at every recursive step happens to be the extreme element (minimum or maximum) of the remaining subarray.
When this occurs, the partition is maximally unbalanced:
- One subproblem has size $0$ .
- The other subproblem has size $n - 1$ .
- The partition step takes $\Theta(n)$ comparisons.
The recurrence relation is:
$T(n) = T(n-1) + \Theta(n).$
Solving this recurrence yields:
$T(n) = \Theta(n^2).$
Therefore, the tightest upper bound for the worst-case time complexity is $O(n^2)$ (option A).

Final answer

Common trap

Confusing average-case performance O(n log n) with worst-case performance O(n^2).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 3
Question: 24 of 65, printed as CS Q.14
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source