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 (n2)
B.	The running time to compute Fn using memoization	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.	Θ{ϕn}

Choose the correct answer from the options given below:

The correct answer is ​ A - IV, B - III, C - II, D - I

Key Points

• A. The running time of a straightforward recursive algorithm to compute the n^th Fibonacci number is exponential in the worst case, which can be represented as O(2^n) (this complexity is larger than any options provided). But, as an approximation, we can denote this as Θ{ϕⁿ}, where ϕ is the golden ratio. So, A matches with IV.
• B. Using memoization (or dynamic programming), the time complexity of calculating the n^th Fibonacci number will become linear, i.e., O(n), because we store and reuse the results of the sub-problems. So, B matches with III.
• C. When we use the matrix exponentiation method to compute Fibonacci numbers, the running time is O(log n), as it computes the nth Fibonacci number by performing only integer addition and multiplication using the matrix [[1,1], [1,0]]. So, C matches with II.
• D. The time complexity of determining an optimal bitonic tour is quadratic as it involves computations for each pair of points so Θ(n^2) is applicable. So, D matches with I.