Question $78$

Identify the average case runtime complexity of a program that computes Fibonacci Numbers

recursively, but also stores solutions of subproblems to reduce runtime complexity. Choose the best

answer.

$O(n^{{?}^{{?}^{?}}}2)$

$O(n)$

$O(2^{{?}^{{?}^{?}}}n)$

$(1)$

$O(logn)$

$O(nlogn)$