Question

Match the algorithms with their times complexities:
List - I (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 $\times$ n matrices

List II.
(i) $\Theta$($n^2$)
(ii) $\Theta$(n log n)
(iii) $\Theta$($2^n$)
(iv) $\Theta$(log n)

• A. P - (iv), Q - (iii), R - (ii), S - (i)
• B. P - (iv), Q - (iii), R - (i), S - (ii)
• C. P - (iii), Q - (iv), R - (ii), S - (i)
• D. P - (iii), Q - (iv), R - (i), S - (ii)

Answer 1

The correct option is C P - (iii), Q - (iv), R - (ii), S - (i)

$\bullet$ Towers of Hanoi with n disks = 2T(n - 1) +1 = $\Theta$($2^n$)
$\bullet$ Binary search given n sorted number = T(n/2) + 1 = $\Theta$(log n)
$\bullet$ Heap sort given n number at the worst case = 2T(n/2) + n = $\Theta$(n log n)
$\bullet$ Adition of two n $\times$ n matricies = 4T(n/2) + 1 = $\Theta$($n^2$).