Question

Match the algorithms with their time complexities:

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

1. P – (iii), Q – (iv), R – (i), S – (ii)
2. P – (iv), Q – (iii), R – (i), S – (ii)
3. P – (iii), Q – (iv), R – (ii), S – (i)
4. P – (iv), Q – (iii), R – (ii), S – (i)

Answer 1

Correct Answer - Option 3 : P – (iii), Q – (iv), R – (ii), S – (i)

• Recurrence relation for tower of Hanoi problem is T (n) = 2 T (n - 1) + 1, So, time complexity for tower of Hanoi problem is Θ (2ⁿ).
• Binary search algorithm searches a sorted array by repeatedly dividing the search interval in half. If value of search key is less than the item in middle, search in the lower half otherwise, search in upper half. In this way, time complexity of binary search in sorted array becomes Θ (log n).
• Heap sort algorithm worst case time complexity is Θ (n log n).
• Addition of two n × n matrices takes Θ (n²) time to execute. As there are two for loop used while addition of two n × n matrices.