*So here is the solution. I repeat questions for easy reading*

Let me introduce you The Very Bad Fibonacci Implementation:

```
function fib(n) {
if (n <= 1) {
return 1
}
return fib(n - 2) + fib(n - 1)
}
```

The first question is very simple:

Q1.What's wrong with this implementation and how to fix it?

### Answer

The implementation recalculates one number multiple times making a lot of unnecessary work. More efficient implementation is just a simple `for`

-loop:

```
function betterFib(n) {
let r1 = 1;
let r2 = 1;
for (let i = 2; i <= n; i++) {
const _r2 = r2;
r2 = += r1;
r1 = _r2;
}
return r2;
}
```

It's not “functionally pure”, it doesn't look like nicely translated math formula. But it works fast!

Q2.What's it complexity in terms of Big O? How to estimate and prove it?

### Answer

It's exponential. However, it doesn't look like precisely
$O(2^n)$
because not every call produces 2 recursive calls, and that's because “left” recursive call `fib(n - 2)`

reaches the recursion base faster than the “right” one. Let's try to sketch an invocation tree:

*drawn with Sketchpad*

It looks like some fancy figure with exponential non-equal sides 😄 And the task is equivalent to calculating its “area”. I'm not sure there's an easy way to calculate it accurately, however, it's possible to estimate its bounds!

- If sides were equal, and the figure height was equal to that of the
**left**side of the original figure, the resulting area would be the order of $O(2^{n/2})$ - If sides were equal, and the figure height was equal to that of the
**right**side of the original figure, the resulting area would be the order of $O(2^n)$

And that's the answer! The complexity
$x$
of the original function `fib`

is within an interval:

Thanks for reading this solution. Double thanks if you've read the post with the problem statement. Triple thanks if you've given it a try! If you find this kind of stuff interesting please consider leaving some feedback, so I will continue to publish short and fun programming exercises. Thanks 🙏

## Discussion (0)