How to calculate the time complexity of a recursive function

To calculate the time-complexity of a recursive function, try to answer the following questions:

• How many times does a function call itself (t)?
• How many times is a function being recursed (k)?

Based on that, we can say that the time complexity of a plain recursive solution is exponential O(t^k). If we draw a recursive tree, we can find the time complexity by summing up the number of nodes in the tree.

Fibonacci Sequence

To find the nth Fibonacci number, we need to sum up two previous Fibonacci numbers.

F(n) = F(n − 1) + F(n − 2)

The function is being called two times:

• F(n-1)
• F(n-2)

Then it’s being recursed n times from n to 0, where n is the depth of the recursive tree for the function. So, the time complexity of the plain recursive solution is O(2^n).

Let’s calculate the time complexity of the function to see if the statement above is true. Let’s denote T(n) as a function to calculate the time complexity of the Fibonacci Sequence.

T(n) = T(n-1) + T(n-2) + C,

where T(n − 1) and T(n − 2) are the time complexities to find (n-1)th Fibonacci and (n-2)th Fibonacci numbers respectively, and C is the number of constant operations performed inside the recursive call.

For simplicity let’s assume that T(n − 2) ≤ T(n − 1).

T(n) = 2×T(n-1) + C

T(n-1) = 2×T(n-2) + C

T(n) = 2×(2×T(n-2) + C) + C

T(n) = 2^2×T(n-2) + 3C

T(n-2) = 2×T(n-3) + C

T(n) = 2^2×(2×T(n-3) + C) + 3C

T(n) = 2^3×T(n-3) + 7C

T(n) = 2^k×T(n-k) + (2^k-1)×C

T(0) = 1

n-k = 0

n = k

T(n) = 2^n×T(0) + (2^n-1)×C = 2^n+(2^n-1)×C

The upper bound time complexity is O(2^n).

Thank you