mshereef's blog

Dynamic Programming Memoization Time Complexity
By mshereef, history, 3 years ago, In English

I was watching this lecture from MIT on dynamic programming, at the 22nd minute, the lecturer said that the formula for calculating the time complexity for a recursive dynamic programming solution using memoization is equal to the number of subproblems * the time of each subproblem without the recursive work.

I am having trouble understanding why this formula is true.

I understand the time complexity of a bottom-up solution because the loops make it obvious, but this top-down using memoization I find a bit confusing.

So if anyone cane share an intuitive way of understanding this formula it would be great.

Thank you in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Consider all the subproblems you will need for some problem(i.e. for fibo you need all of the subproblems from 0 to n). Let's say you write fibo like:

int fibo(int n)
{
    if(n<2)
        return n;
    return fibo(n-1)+fibo(n-2);
}

Without memoization the code has O(2^N) complexity, because you have ~2^N calls. However, when memoizing you don't calculate a subproblem multiple times, only once. So after you solve fibo(n-1) in some time complexity, fibo(n-2) is already calculated so it's time complexity is O(1), instead of O(2^N). Because one of the subproblems is calculated in O(1), it can be ignored, leaving us with just one call. That call has some complexity depending(only) on fibo(n-2), which is calculated based(only) on fibo(n-3), ... giving you the complexity for fibo(n)=O(n). This is because the subproblems needed aren't computed multiple times, only once, so the function's complexity is just the time it takes to merge the subproblems * the ammount of subproblems. In the case of fibo, merging is done in constant time and number of subproblems is n.

I hope it helped.

→ Reply