DEV Community

Cover image for Understanding The O(2^n) Time Complexity
bankymono
bankymono

Posted on

Understanding The O(2^n) Time Complexity

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)
Enter fullscreen mode Exit fullscreen mode

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.

funOne of 5

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.
General case

The second function definition...

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

funTwo(6)
Enter fullscreen mode Exit fullscreen mode

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

Let us visualize the function calls when n = 6

version-2

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

general case, v2

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)
}
Enter fullscreen mode Exit fullscreen mode

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.
Alt Text

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;
Enter fullscreen mode Exit fullscreen mode

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

Alt Text

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
Alt Text

Therefore the total number of calls would be
Alt Text

where n is 5.

For a general case of n, where n is the input to the function above the time complexity is
Alt Text
If we eliminate the constant, the time complexity would be
Alt Text

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)
}

Enter fullscreen mode Exit fullscreen mode

This time we are subtracting 2.
Visualizing the function calls when n = 8
Alt Text
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
Alt Text
Which is simplified to
Alt Text

The fibonacci function

Now that we have established that funThree and funFour above both have time complexity of
Alt Text
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
Alt Text

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)
}
Enter fullscreen mode Exit fullscreen mode

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

Alt Text

That means time complexity of the fibonacci function is therefore exactly

Alt Text

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.

Top comments (0)