Understanding The O(2^n) Time Complexity
Tags: javascript, codenewbie, programming, algorithms
Published: 2021-03-16 10:43:02

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 <img src="https://latex.codecogs.com/png.latex?2^n" title="2^n" />(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

```javascript
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.

![funOne of 5](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e1emggrreu4aiqyc3xae.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qtxumucdn6egimh0afid.png)

####The second function definition...####

```javascript
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*** 

![version-2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/d4o9e2yurl1i5uqprh7s.png)

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

![general case, v2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mr083vsec74ggvnuyfem.png)

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'.

```javascript
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.
 ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qwhkr6onkxpai0q9i44q.png)

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

```javascript
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.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/321co041p567vhfbf2y5.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1sgnoi2pmb62z89l0r9c.png)

Therefore the total number of calls would be
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/33i0r22y5at1elfa1tc4.png)

 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6dzzq8a3y5t7ewaz59l9.png)
If we eliminate the constant, the time complexity would be 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y2156h8y28w3xoomkz6v.png)

####The fourth function definition...####
Let us consider a final function before looking at the fibonacci function itself.

```javascript
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***
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w30f347mwb246bt9g38j.png)
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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/egbwhgyypiub4mhl1dr3.png)
Which is simplified to 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y2156h8y28w3xoomkz6v.png)

####The fibonacci function####
Now that we have established that **funThree** and **funFour** above both have time complexity of 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y2156h8y28w3xoomkz6v.png)
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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y2156h8y28w3xoomkz6v.png)

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

```javascript
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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/svd5t0j2hbcblmbi3h4j.png)

That means time complexity of the fibonacci function is therefore exactly

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y2156h8y28w3xoomkz6v.png)

###That's it...###
For a more interesting explanation, check out this video on [Dynamic Programming](https://www.youtube.com/watch?v=oBt53YbR9Kk&t=6s) from [freecodecamp](https://www.freecodecamp.org/). This article is an adaptation of the fibonacci example in the video. I hope you found it helpful.
Thank you for reading through.