Match the algorithms with their time complexities:
2017
Match the algorithms with their time complexities:
- A.
\(P\rightarrow (iii) \quad Q \rightarrow(iv) \quad r \rightarrow(i) \quad S \rightarrow(ii)\) - B.
\(P\rightarrow (iv) \quad Q \rightarrow(iii) \quad r \rightarrow(i) \quad S\rightarrow(ii)\) - C.
\(P\rightarrow (iii) \quad Q \rightarrow(iv) \quad r \rightarrow(ii) \quad S\rightarrow(i)\) - D.
\(P\rightarrow (iv) \quad Q \rightarrow(iii)\quad r \rightarrow(ii) \quad S\rightarrow(i)\)
Attempted by 227 students.
Show answer & explanation
Correct answer: C
Final matching:
Towers of Hanoi → Θ(2^n). Reason: the recurrence T(n) = 2T(n−1) + 1 (move n−1 disks twice plus one move) yields exponential time.
Binary search → Θ(log n). Reason: each comparison halves the search space, giving logarithmic time.
Heap sort (worst case) → Θ(n log n). Reason: building a heap is O(n) and performing n extract-max operations costs O(n log n) in total.
Addition of two n × n matrices → Θ(n^2). Reason: you perform one scalar addition for each of the n^2 entries.
Therefore the correct mapping is: Towers of Hanoi → (iii), Binary search → (iv), Heap sort → (ii), Addition of two n × n matrices → (i).
A video solution is available for this question — log in and enroll to watch it.