GATE CS 1996 Q2.15 — Searching, Sorting, Hashing

In Quick-sort, when the first element is chosen as the pivot:

1. Input (i) is already sorted: $1, 2, 3, \dots, n$
   The pivot is the smallest element ($1$). Partitioning requires comparing the pivot with the remaining $n-1$ elements. This splits the array into an empty left subarray and a right subarray of size $n-1$.
   The recurrence relation for the number of comparisons is: $$T(n) = T(n-1) + (n-1)$$
2. Input (ii) is reverse sorted: $n, n-1, n-2, \dots, 1$
   The pivot is the largest element ($n$). Partitioning requires comparing the pivot with the remaining $n-1$ elements. This splits the array into a left subarray of size $n-1$ and an empty right subarray.
   The recurrence relation for the number of comparisons is: $$T(n) = T(n-1) + (n-1)$$

Since both cases result in the same highly unbalanced partition at every recursive step (splitting into sizes $0$ and $k-1$ for an array of size $k$), the total number of comparisons is identical:

Therefore, $C_1 = C_2$.