Loading practice questions
What is the time complexity of the recursive implementation used to find the nth fibonacci term?
Correct Answer: D — Exponential
Explanation:
The recurrence relation is given by (fibo(n) = fibo(n - 1) + fibo(n - 2)). So, the time complexity is given by:
(T(n) = T(n - 1) + T(n - 2))
Approximately,
T(n) = 2 * T(n - 1)
= 4 * T(n - 2)
= 8 * T(n - 3)
:
:
:
= 2^{k} * T(n - k)
This recurrence will stop when n - k = 0
i.e. n = k
Therefore, (T(n) = 2^{n} * O(0) = 2^{n})
Hence, it takes exponential time.
It can also be proved by drawing the recursion tree and counting the number of leaves.