1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
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 × n matrices List II. (i) Θ(n2) (ii) Θ(n log n) (iii) Θ(2n) (iv) Θ(log n)

A
P - (iv), Q - (iii), R - (ii), S - (i)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
P - (iv), Q - (iii), R - (i), S - (ii)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
P - (iii), Q - (iv), R - (ii), S - (i)
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
D
P - (iii), Q - (iv), R - (i), S - (ii)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
Open in App
Solution

## The correct option is C P - (iii), Q - (iv), R - (ii), S - (i)∙ Towers of Hanoi with n disks = 2T(n - 1) +1 = Θ(2n) ∙ Binary search given n sorted number = T(n/2) + 1 = Θ(log n) ∙ Heap sort given n number at the worst case = 2T(n/2) + n = Θ(n log n) ∙ Adition of two n × n matricies = 4T(n/2) + 1 = Θ(n2).

Suggest Corrections
0
Join BYJU'S Learning Program
Related Videos
Extrema
MATHEMATICS
Watch in App
Explore more
Join BYJU'S Learning Program