Match List I with List II LIST ILIST II A. The running time of straight forward recursive method to…
Plain recursion recomputes the same subproblems, and its running time grows like \(F_n\) itself, that is \(\Theta(\Phi^n)\). Memoization computes each \(F_i\) once, giving…
Choose your answer
Match List I with List II
| LIST I | LIST II |
|---|---|
| A. The running time of straight forward recursive method to compute nth Fibonacci number Fn | I. O(n²) |
| B. The running time to compute Fn using memorization | II. O(lg n) |
| C. The running time to compute Fibonacci number Fn using only integer addition and multiplication | III. O(n) |
| D. The running time to determine an optimal bitonic tour | IV. Θ(Φⁿ) |
Answer and explanation
Correct answer B
Plain recursion recomputes the same subproblems, and its running time grows like itself, that is . Memoization computes each once, giving O(n). Using only integer additions and multiplications, can be read off the nth power of the 2 × 2 matrix [[1, 1], [1, 0]], found by repeated squaring in O(lg n) arithmetic operations, and the dynamic program for an optimal bitonic tour fills an n × n table in O(n²) time. Matching naive recursion with O(n²) fails because its recursion tree grows exponentially, not quadratically.
Practice for these exams
-
UGC NET Computer Science and Applications