GATE CS 2015 Set 1 Q2 — Searching, Sorting, Hashing

The worst-case time complexity of the Quicksort algorithm occurs when the pivot element consistently partitions the array into highly unbalanced subproblems. This typically happens when the array is already sorted (or reverse-sorted) and the first or last element is chosen as the pivot.

In this worst-case scenario:

• The array of size $n$ is partitioned into one subproblem of size $n-1$ and another of size $1$.
• The partitioning step itself takes linear time, represented as $cn$ (where $c$ is a constant).

Thus, the recurrence relation representing this behavior is:

$$T(n) = T(n-1) + T(1) + cn$$

Solving this recurrence yields the worst-case time complexity of $O(n^2)$.

Elimination of other options:

• Option A: $T(n) = 2T(n/2) + cn$ represents the best-case (or average-case) recurrence of Quicksort, where the pivot always divides the array into two equal halves, yielding $O(n \log n)$ complexity.
• Option C: $T(n) = 2T(n-1) + cn$ would result in an exponential time complexity $O(2^n)$, which is incorrect.
• Option D: $T(n) = T(n/2) + cn$ represents a binary-search-like reduction with linear work, yielding $O(n)$ complexity.