How to mathematicaly prove the Time Complexity of the recursive Fibonacci program with Memoization

Question

Well, I am looking for a more mathematical approach to things. Using this two-analysis approach.

For the standard Fibonacci recursive function, we all know that it runs with time complexity O(2^n) the proof found by upper bound :

T(n-1)=T(n-2)

T(n)=2T(n-1)+c   

    =4T(n-2)+3c

    =8T(n-3)+7c

    =2^k T(n-k)+(2^k-1)c

n - k = 0 , hence k = n

T(n) = 2^n T(0) + (2^n - 1)c

T(n) = (1 + c) * 2^n - c

T(n) <= 2^n 

I tried to optimize this time, I used the Memoization approach of Dynamic Programming in the following code :

private static long fib(int n) {
    if (n <= 1) return n;
    
    if (memo[n] != 0) {
        return memo[n];
    }
    
    long result = fib(n - 1) + fib(n - 2);
    memo[n] = result;
    
    return result;
}

I know that looking at, and by trying some n the n value; this code is much better. And also that the time complexity dropped to O(n).

I want to do the same proof thing for this code using upper/lower bounds to prove this, but I don't know how to start.

The thing to say, I am doing this to see where my worst and best scenarios are.

Answer 1

The relationship between the elements of the sequence doesn't change. T(n) would be still expressed in the same way:

T(n) = T(n - 1) + T(n - 2)

And

T(n - 1) = T(n - 2) + T(n - 3)

And

T(n - 2) = T(n - 3) + T(n - 4)

And so on, until recursion hit the base case: T(0) = c and T(1) = c.

What changes when you're applying Memoization is the number of recursive calls. It would be 2 * n instead of 2ⁿ. And every repeated recursive call (like T(n - 2) and T(n - 3) above) would now have a constant time complexity.

It would be more apparent if you would draw a tree of recursive calls on a paper, then you would observe that branches on one side of the tree turned into a leaves (because the result of these calls was already computed, and we don't propagate them further).

Here's such a tree of call for plain recursion:

                t(n)   Naive reqursive implementation
               /    \  2 ^ n recursive calls
              /      \
           t(n-1)    t(n-2)
          /   \        /  \
         /     \      /    \
   t(n-2)   t(n-3)  t(n-3)  t(n-4)
   /   \     /  \    /  \    /  \
  .................................
   t(2)
  /   \
t(1)  t(0)

And that's how it changes if we apply Memoization:

                t(n)   Memoization
               /    \  ~ 2 * n recursive calls
              /      \
           t(n-1)    t(n-2)
           /   \
          /     \
     t(n-2)    t(n-3)
     /   \ 
  .................................
   t(2)
  /   \
t(1)  t(0)

I.e.

T(n) = T(n - 1) + c = T(n - 2) + 2 * c = T(n - 3) + 3 * c = ... = T(1) + n * c

Which would give T(n) = O(n)