Question

Consider the following implementation of a Fibonacci calculator:

def fibonacci(x):
if (x <= 2):
return 1
return fibonacci(x-1) + fibonacci(x-2)
This function has a known runtime complexity of O(2^x).

The usage of Dynamic Programming can greatly improve this runtime complexity. Consider this revised implementation:

cache = dict()
def fibonacci(x):
if (x in cache):
return cache[x]

if (x <= 2):
return 1

cache[x] = fibonacci(x-1) + fibonacci(x-2)
return cache[x]
Which statement most correctly describes the tradeoffs?

Select the best option:
A.
The implementation is strictly better; runtime complexity improves to O(x^2) and reduces space complexity by O(x)

B.
The implementation is faster; runtime complexity improves to O(x^2) while space stays the same since it trades stack space for memory

C.
The implementation is heavier; runtime complexity may or may not improve depending on rate of cache hits, but space complexity increases to O(x)

D.
The implementation is faster but heavier; Runtime complexity improves to O(x), using up an additional O(x) of space

E.
The implementation should be faster, but there is a bug that causes it to be just as slow as the original implementation.​

Answer 1

Answer:

its very tough question pls ask your teacher

Answer 2

Answer:

Explanation:

A