CODEWITHSUNDEEP
big-ofibonaccimemoization
Jimbo
Jimbo

Reputation: 1781

Big O Notation - O(N) Fibonacci Generator

Just brushing up on my big O in advance of an interview.

On pages 53 and 54 of cracking the coding interview (6th ed), in the chapter on big O, you will see example 15, which appears as follows.

void allFib(int n){
    int[] memo = new int[n+1];
    for(int i=0; i<n; i++){
        System.out.println(i + ":" + fib(i,memo));
    }
}

int fib(int n, int[] memo){
    if(n<=0) return 0;
    else if(n==1) return 1;
    else if(memo[n]>0) return memo[n];

    memo[n]=fib(n-1,memo)+fib(n-2,memo);

    return memo[n];
}

Long story short, this is a standard approach, which uses memoisation to ensure fib values only have to be calculated once. But they still have to be calculated once and calculating them is O(2^N) temporal complexity.

The book is saying that because we can retrieve the fib values in constant time from the memo that the algorithm is O(N).

It does not explain why it is we can ignore the fact that you do have to derive the values once from an exponential function. Is amortisation being applied?

I trust the book, but the explanation provided isn't helping me to understand why the temporal complexity is O(N) in this case.

Post Edit:

Let me put this another way.

How could calling fib n times be O(N)... int[] memo = new int[n+1];

for(int i=0; i<n; i++){
    System.out.println(i + ":" + fib(i,memo));
}

...when calling it once is O(N^2)?

fib(n,memo)

Final Edit: Thanks all. I have my answer. Even the single call to the fib method benefits from memoisation and thus is not O(N^2), it too is O(N).

Upvotes: 1

Views: 642

Answers (2)

David Soroko
David Soroko

Reputation: 9096

One way to look at this is that in memo[n]=fib(n-1,memo)+fib(n-2,memo) when fib(n-1, memo) returns, the value needed by fib(n-2,memo) is already stored in memo ( if(memo[n]>0) return memo[n] ), this is repeated at every recursion level.

So instead of the call graph looking like this (for the naive version):

        *
       * *
      * * * * 
  * * * * * * * *

It looks like this

         *
        * * 
       * *   
      * *

Upvotes: 1

Alex
Alex

Reputation: 1957

It's O(N) because you only calculate each value once and reuse the calculated value later. E.g. for fib(4) this would be the call stack:

fib(4) = fib(3) + fib(2);
    fib(3) = fib(2) + fib(1);
        fib(2) = fib(1) + fib(0); // value stored
            fib(1) = 1;
            fib(0) = 1;
    fib(2) = 2; // value accessed

The stored value is accessed when it's already calculated.

When you have a look a look at the "lazy implementation" of the Fibonacci numbers:

int fib(int i) {
    if(i <= 1) return 1;
    return fib(i - 1) + fib(i - 2);
}

You need to calculate a lot of numbers more than once. E.g. again for fib(4) the call stack would look like:

fib(4) = fib(3) + fib(2);
    fib(3) = fib(2) + fib(1);
        fib(2) = fib(1) + fib(0);
            fib(1) = 1;
            fib(0) = 1;
    fib(2) = fib(1) + fib(0);
        fib(1) = 1;
        fib(0) = 1;

As you can see, fib(2), fib(1) and fib(0) need to be calculated more than once. With your memory approach, you only calculate each new value once. Also, keep in mind that the call stack gets exponentially bigger with higher Fibonacci values which leads to even more "double calculation" of numbers. That's why this lazy approach has O(2^N) and the memory approach is O(N).

HTH

Upvotes: 0

Related Questions