GATE CS 2014 Set 3 Q14 — Searching, Sorting, Hashing

The correct option is A.

In Quicksort, the worst-case time complexity occurs when the pivot selection consistently results in highly unbalanced partitions (e.g., one partition of size $0$ and the other of size $n-1$ at each step).

Even if we choose the central element of the array as the pivot, we can always construct an adversarial input sequence where the central element is always the minimum (or maximum) element of the current subarray.

For such an input, the recurrence relation for the running time is:

$$T(n) = T(n-1) + T(0) + \Theta(n)$$

Solving this recurrence yields:

$$T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$$

Thus, the tightest upper bound for the worst-case performance remains $O(n^2)$.