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.

Θ{ϕⁿ}

Choose the correct answer from the options given below:

Question

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.	Θ{ϕⁿ}