Match List I with List II
| List I | List II |
|---|---|
| A. Running time of a straightforward recursive method to compute the nth Fibonacci number Fₙ | I. O(n²) |
| B. Running time to compute Fₙ using memoization | II. O(log n) |
| C. Running time to compute Fₙ using only integer addition and multiplication | III. O(n) |
| D. Running time to determine an optimal bitonic tour | IV. Θ(φⁿ) |
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. A-IV, B-III, C-II, D-I
Explanation
The naive recursive Fibonacci runs in Θ(φⁿ) (IV). With memoisation it is O(n) (III). Using only integer addition and multiplication (matrix powering) it is O(log n) (II). The optimal bitonic tour DP is O(n²) (I).More Data Structures and Algorithms questions
- Statement I: If f and g are two functions and f = O(g) but g ≠ o(f), we say that the growth rate of g is smaller than that of f. Statement…
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: It is possible to create…
- For each function below, let n be the least integer such that f(x) is O(xⁿ). Arrange the functions in increasing order of n: A. f(x) = 3x³…
- f(n) = a·f(n/b) + g(n) is a divide-and-conquer recurrence. Match the algorithms in List I with their recurrences in List II.List I List II…
- The height of a binary search tree built by inserting the words banana, peach, apple, pear, coconut, mango and papaya (in this order, alpha…
- How much time does an algorithm using 2⁵⁰ bit operations need if each bit operation takes 2⁻³⁸ seconds?