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?

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 🙏