CODEWITHSUNDEEP
javascriptalgorithmmemoization
Olena Horal
Olena Horal

Reputation: 1214

How to explain cached fibonacci algorithm complexity

I'm trying to explain correctly cached fibonacci algorithm complexity. Here is the code (https://jsfiddle.net/msthhbgy/2/):

function allFib(n) {
  var memo = [];
  for (var i = 0; i < n; i++) {
    console.log(i + ":" + fib(i, memo))
  }
}

function fib(n, memo) {
  if (n < 0) return 0;
  else if (n === 1) return 1;
  else if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

allFib(5);

The solution is taken from "Cracking the coding interview" and adapted to javascript. So here is a "not very nice" tree of function calls

function calls tree

I was thinking like that: "The left most branch (bold one) is where the evaluation is happening" and it is definitely the number passed to the allFib function for the first time. So the complexity is O(n). Everything that is to the right will be taken from cache and will not require extra function calls". is it correct? also how to connect this to the tree "theory". The depth and the height of the tree in this case is 4 but not 5 (close to n but not it). I want the answer to be not intuitive but more reliable.

Upvotes: 1

Views: 326

Answers (2)

trincot
trincot

Reputation: 350310

Here is a function that really uses the cache:

function Fibonacci() {
  var memo = [0, 1];

  this.callCount = 0;

  this.calc = function(n) {
    this.callCount++;
    return n <= 0 ? 0 
         : memo[n] || (memo[n] = this.calc(n - 1) + this.calc(n - 2));
  }
}

var fib = new Fibonacci();

console.log('15! = ', fib.calc(15));
console.log('calls made: ', fib.callCount);
fib.callCount = 0; // reset counter
console.log('5! = ', fib.calc(5));
console.log('calls made: ', fib.callCount);
fib.callCount = 0;
console.log('18! = ', fib.calc(18));
console.log('calls made: ', fib.callCount);

The number of function calls made is:

(n - min(i,n))*2+1

Where i is the last entry in memo.

This you can see as follows with the example of n = 18 and i = 15:

The calls are made in this order:

calc(18)
calc(17)   // this.calc(n-1) with n=18
calc(16)   // this.calc(n-1) with n=17
calc(15)   // this.calc(n-1) with n=16, this can be returned from memo
calc(14)   // this.calc(n-2) with n=16, this can be returned from memo
calc(15)   // this.calc(n-2) with n=17, this can be returned from memo
calc(16)   // this.calc(n-2) with n=18, this can be returned from memo

The general pattern is that this.calc(n-1) and this.calc(n-2) are called just as many as times (of course), with in addition the original call calc(n).

Here is an animation for when you call fib.calcfor the first time as fib.calc(5). The arrows show the calls that are made. The more to the left, the deeper the recursion. The bubbles are colored when the corresponding result is stored in memo:

Fibonacci animation

This evidently is O(n) when i is a given constant.

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386654

First, check for negative n, and move the value to zero.

Then check if a value is cached, take the value. If not, assign the value to the cache and return the result.

For the special cases of n === 0 or n === 1 assign n.

function fibonacci(number) {
    function f(n) {
        return n in cache ?
            cache[n] :
            cache[n] = n === 0 || n === 1 ? n : f(n - 1) + f(n - 2);
    }

    var cache = [];
    return f(number);
}

console.log(fibonacci(15));
console.log(fibonacci(5));

Part with predefined values in cache, as Thomas suggested.

function fibonacci(number) {
    function f(n) {
        return n in cache ?
            cache[n] :
            cache[n] = f(n - 1) + f(n - 2);
    }

    var cache = [0, 1];
    return f(number);
}

console.log(fibonacci(15));
console.log(fibonacci(5));

Upvotes: 0

Related Questions