javascriptalgorithmdata-structurestime-complexity# I have trouble understanding exponential time complexity

To begin with, here is the main code

```
var fib = function(n) {
if (n===0) return 0
if (n===2 || n===1) return 1
return fib(n-1) + fib(n-2)
};
```

so the question is to print the Fibonacci number, Now letting go of the logic of the question, I can see that whenever we increase the variable n by 1, the function will be called **2 * n** times, so even when we consider backtracking of the function by returning the variables it would be **4 * n** major operations, and according to the definition of exponential times time complexity, the number of operations should double every time we increase the input variable and I think it is not the case in here.

Solution

For the naive Fibonacci implementation we do indeed find exponential time complexity (or more exactly O(2^n)), most readily apparent by looking at a tree graph of the function calls.

```
F_5
/ \
F_3 F_4
/ \ / \
F_1 F_2 F_3 F_2
/ \
F_2 F_1
```

You can clearly see how the number of execution doubles in each line (1, 2, 4,...)

To convince yourself, draw this diagram for `F_6`

(and `F_7`

if needed).

definition of exponential times time complexity, the number of operations should double every time we increase the input variable

No, exponential time complexity means O(b^n), where n is the length of the input variable. It only doubles each time if `b=2`

. However, you can have `b=3`

(triples every time), `b=4`

(quadruples) or `b=1.2213`

, you get the point.

We can also write code that counts it for us:

```
var counter = 0;
function fib(n){
counter++;
if( n <= 1 ){
return 1;
}
return fib(n-1) + fib(n-2);
}
for( var i = 0; i < 15; ++i ){
counter = 0;
fib(i);
console.log("Fib evaluations for " + i + ": " + counter);
}
```

If you do a logarithmic plot of the counter you get the following picture, confirming the exponential increase in execution time:

- How not to overwrite user data in FireStore for returning user when login using Angularifre?
- using spread operator in typescript
- javascript postMessage not working
- Is there a way to add/remove several classes in one single instruction with classList?
- Appending .js extension on relative import statements during Typescript compilation (ES6 modules)
- How do I "preventDefault" for custom events
- React Hooks useState+useEffect+event gives stale state
- How to check if a string ONLY contains specific strings
- How to prevent changes to a prototype?
- Creating a textarea with auto-resize
- Javascript file upload - PDF to image(s)
- Truncate number to two decimal places without rounding
- How browsers store data for autocomplete and where?
- Debt Snowball Function
- JSON Web Token (JWT) Error: Invalid Signature with RSA Key Pairs
- What a RegEx that can match text in parentheses with nested parentheses
- How would I get the full response from this Axios request?
- next js - the style of the tailwind class i get from API doesnt apply on my element
- How can I disable sort on a specific element?
- Is it a bad idea to use the meta tag in HTML to specify custom metadata for retrieval with JavaScript?
- Detecting when user scrolls to bottom of div with React js
- Mongoose partial update of an object
- in javascript, how do you sort a subset of an array?
- Firebase email link authentication leads to a page that says "Error encountered" - "The selected page mode is invalid"
- How to fire window.scrollY only one time
- How to call a method from child component to parent one in vue2?
- Switch value for clicked button from group of buttons in jQuery
- Smooth scroll to specific div on click
- How to use MaterializeCss with Vue.js?
- Can't find variable: React