## DEV Community is a community of 550,319 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Solution to the simple task on algorithm complexity

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?

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?

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: 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:

$O(2^{n/2}) < x < O(2^n)$

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 