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

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.

CodePudding user response：

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)