Printing this content is disabled

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.