GATE CS 2017 Set 2 Q.3 (CS Q.3): Asymptotic Analysis and Time/Space Complexity

Match the algorithms with their time complexities:

Algorithm	Time complexity
(P) Towers of Hanoi with $n$ disks	(i) $\Theta(n^2)$
(Q) Binary search given $n$ sorted numbers	(ii) $\Theta(n \log n)$
(R) Heap sort given $n$ numbers at the worst case	(iii) $\Theta(2^n)$
(S) Addition of two $n \times n$ matrices	(iv) $\Theta(\log n)$

P $\to$ (iii), Q $\to$ (iv), R $\to$ (i), S $\to$ (ii)

P $\to$ (iv), Q $\to$ (iii), R $\to$ (i), S $\to$ (ii)

P $\to$ (iii), Q $\to$ (iv), R $\to$ (ii), S $\to$ (i)

P $\to$ (iv), Q $\to$ (iii), R $\to$ (ii), S $\to$ (i)

Official answer and solution

Solution

Identify the standard worst-case time complexities of the four algorithms.

Analyze each algorithm:

(P) Towers of Hanoi with $n$ disks: The recurrence is $T(n) = 2T(n-1) + 1$ , which gives $T(n) = 2^n - 1 = \Theta(2^n)$ . This matches (iii).
(Q) Binary search on $n$ sorted numbers: Halves the search space at each comparison, giving recurrence $T(n) = T(n/2) + O(1)$ , so $T(n) = \Theta(\log n)$ . This matches (iv).
(R) Heap sort on $n$ numbers (worst case): Building the heap takes $O(n)$ , and each of the $n$ extractions takes $O(\log n)$ heapify time, yielding a worst-case time complexity of $\Theta(n \log n)$ . This matches (ii).
(S) Addition of two $n \times n$ matrices: Requires adding $n \times n = n^2$ pairs of corresponding elements, taking $\Theta(n^2)$ time. This matches (i).

Combining the matches gives P $\to$ (iii), Q $\to$ (iv), R $\to$ (ii), S $\to$ (i), matching option C.

Final answer

Common trap

Confusing matrix addition (which is $O(n^2)$ ) with standard matrix multiplication (which is $O(n^3)$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.