DEV Community is a community of 797,169 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: • 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)$