GATE CS 2016 Set 1 Q13 — Searching, Sorting, Hashing

To find the worst-case running times of the three sorting algorithms, we analyze each individually:

1. Insertion Sort: In the worst case (when the input array is sorted in reverse order), each element must be compared with and shifted past all previously sorted elements. The total number of comparisons is: $$1 + 2 + 3 + \dots + (n-1) = \frac{n(n-1)}{2} = \Theta(n^2)$$
2. Merge Sort: Merge sort is a divide-and-conquer algorithm that always divides the array into two equal halves, sorts them recursively, and merges them. Its recurrence relation in all cases (best, average, and worst) is: $$T(n) = 2T(n/2) + \Theta(n)$$ By Master's Theorem, this evaluates to $\Theta(n \log n)$.
3. Quick Sort: In the worst case (e.g., when the array is already sorted or reverse-sorted, and the first or last element is chosen as the pivot), the partition step produces one subproblem of size $0$ and another of size $n-1$. The recurrence relation is: $$T(n) = T(n-1) + \Theta(n)$$ This solves to $\Theta(n^2)$.

Thus, the worst-case running times are $\Theta(n^2)$, $\Theta(n \log n)$, and $\Theta(n^2)$, respectively.