Understanding The O(2^n) Time Complexity

bankymono — Tue, 16 Mar 2021 10:43:02 +0000

Complexities are a way for us to write efficient code,code that runs fast and do not consume much memory. Although there is always a trade-off between writing code that runs fast and memory-consuming code, we need to find a balance.

The time complexity of fibonacci sequence, when implemented recursively is (two to the exponent of n) where 'n' is the nth number of the fibonacci sequence.

How is this derived?

We are going to approach this by first looking at the implementation of four simpler functions. These functions will give us a foundation to understand the time complexity of the fibonacci function. We would lastly look at the fibonacci function.

The first function definition...

Let us start with a simpler case, let us say we have the following function

const funOne = (n) => {
  if(n <= 1) return;
  funOne(n-1)
}

funOne(5)

When funOne(5) is called, since 'n' equals 5 is not a base case, it recursively calls funOne(n-1), which recursively calls funOne(n-2) until n is equal to 1, the function then returns.

Let us visualize the function calls when n = 5

We are going to visualize this in the tree below.

Each node in the tree represent a function call. For n=5, funOne is called 5 times. The time complexity of funOne(5) is O(5) time.
Generalizing for any n passed into funOne(n) the time complexity is O(n) time.

The second function definition...

const funTwo = (n) => {
  if(n <= 1) return;
  lessTwo(n-2)
}

funTwo(6)

This time instead of subtracting 1, we subtract 2 from 'n'.

Let us visualize the function calls when n = 6

Also looking at the general case for 'n', we have

We can say the time complexity for the function is O(n/2) time because there are about n/2 calls for function funTwo. Which is still O(n) when we remove the constant.

The third function definition...

In this function definition, the function recursively calls itself twice with
'n-1'.

const funThree (n) =>{
   if(n <=1) return;

   funThree(n-1)
   funThree(n-1)
}

Visualizing the function calls when n = 5
How do we visualize this? Each function call branches into two recursive calls. Hence the tree would look like the one below for 'n' equals 5.

As seen in the image above, the number of levels in this tree is 5 because 'n' is equal to 5. Hence the number of level for any funThree(n) is 'n'.
On each level, there are a number of calls. Let us breakdown the number of function calls per level.

On level one (funThree(5)), there is 1 function call - (2 ^ 0).
On level two (funThree(4)), there are 2 function calls - (2 ^ 1).
On level three (funThree(3)), there are 2 x 2 function calls - (2^2).
On level four(funThree(2)), there are 2 x 2 x 2 function calls - (2^3)
On level five (funThree(1)), there are 2 x 2 x 2 x 2 function calls - (2 ^ 4).

After funThree(1), there are no more recursive calls because the function returns because of the base case (n <=1).

if(n <=1) return;

The function calls in the last level is the sum of all function call in the levels above it plus one.

So if we sum the bottom level and all the levels above it together, we would almost have 2^5. To be more accurate, the actual answer would be

Therefore the total number of calls would be

where n is 5.

For a general case of n, where n is the input to the function above the time complexity is

If we eliminate the constant, the time complexity would be

The fourth function definition...

Let us consider a final function before looking at the fibonacci function itself.

const funFour (n) =>{
   if(n <=1) return;

   funFour(n-2)
   funFour(n-2)
}

This time we are subtracting 2.
Visualizing the function calls when n = 8

As seen above, the number of levels is about n/2.
Using the same analysis we used for funThree,
we can safely conclude that the time complexity is

Which is simplified to

The fibonacci function

Now that we have established that funThree and funFour above both have time complexity of

we can see that they only differ in how they make their recursive calls, funThree recursively called itself with input 'n-1' and funFour with input 'n-2' and despite their differences, both have time complexity of

With this in mind, let us have a look at the fibonacci function below.

const fibonacci = (n) => {
    if(n < 2) return 1

    return fibonacci(n-1) + fibonacci(n-2)
}

You would agree with me that the fibonacci function above falls right between funThree and funFour functions in the sense that it recursively calls itself with both value (n-1) and (n-2).

As such, the time complexity of the fibonacci function is between time complexities of funThree and funFour as shown below

That means time complexity of the fibonacci function is therefore exactly

That's it...

For a more interesting explanation, check out this video on Dynamic Programming from freecodecamp. This article is an adaptation of the fibonacci example in the video. I hope you found it helpful.
Thank you for reading through.

DEV Community: bankymono