Match the List I with List II A. The running time of straight forward…
2023
Match the List I with List II
A. The running time of straight forward recursive method to compute nth Fibonacci number Fn
B. The running time to compute Fn using memoization
C. The running time to compute Fibonacci number Fn using only integer addition and multiplication
D. The running time to determine an optimal bitonic tour
I. O(n²)
II. O(lg n)
III. O(n)
IV. Θ(Φⁿ)
- A.
A-I, B-III, C-IV, D-II
- B.
A-IV, B-III, C-II, D-I
- C.
A-I, B-II, C-IV, D-III
- D.
A-IV, B-II, C-III, D-I
Attempted by 80 students.
Show answer & explanation
Correct answer: B
A matches IV because straightforward recursion is exponential Θ(Φⁿ). B matches III as memoization reduces complexity to linear O(n). C matches II since matrix exponentiation is logarithmic O(lg n). D matches I because the bitonic tour DP problem requires quadratic time O(n²).
A video solution is available for this question — log in and enroll to watch it.