GATE CS 2017 Set 2 Q03 — Asymptotic Worst Case Time and Space Complexity

We can determine the time complexity of each algorithm as follows:

• P. Tower of Hanoi with $n$ disks: The recurrence relation for the number of moves is given by $T(n) = 2T(n-1) + 1$ with $T(1) = 1$. Solving this recurrence yields $T(n) = 2^n - 1$, which is in $\Theta(2^n)$.
  Thus, P → (iii).
• Q. Binary Search given $n$ sorted numbers: In each step, the search space is halved. The recurrence relation is $T(n) = T(n/2) + \Theta(1)$, which solves to $\Theta(\log n)$.
  Thus, Q → (iv).
• R. Heap sort given $n$ numbers at the worst case: Heap sort consists of building a max-heap (which takes $O(n)$ time) followed by $n$ extractions of the maximum element (each taking $O(\log n)$ time). The overall worst-case time complexity is $\Theta(n \log n)$.
  Thus, R → (ii).
• S. Addition of two $n \times n$ matrices: To add two $n \times n$ matrices, we perform element-wise addition for each of the $n^2$ positions. This requires $n^2$ additions, resulting in a time complexity of $\Theta(n^2)$.
  Thus, S → (i).

Combining these matches, we get: P → (iii), Q → (iv), R → (ii), S → (i), which corresponds to Option C.