Question

Match the algorithms with their time complexities:

Algorithm:
(P) Towers of Hanoi with n disks
(Q) Binary search given n sorted numbers
(R) Heap sort given n numbers at the worst case
(S) Addition of two n × n matrices

Time complexity:
(i) Θ(n²)
(ii) Θ(n log n)
(iii) Θ(2ⁿ)
(iv) Θ(log n)

Accepted Answer

The correct answer is (C) P→(iii), Q→(iv), R→(ii), S→(i). Towers of Hanoi with n disks requires 2ⁿ−1 moves → Θ(2ⁿ) = (iii). Binary search on n sorted elements → Θ(log n) = (iv). Heap sort's worst case is Θ(n log n) = (ii). Adding two n×n matrices touches every one of the n² entries once → Θ(n²) = (i). So P→iii, Q→iv, R→ii, S→i.

Explanation