Upper Bound on Runtime of Memoized DP Algorithms

Question

I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive functions.

However, I am now trying to determine a "Big-O" for a DP problem I've memoized. I don't really care about the answer to this specific problem, but am more interested in a method I can use for other programs I write, or a resource that I can read to learn how to analyze this type of program.

In case a concrete example helps, the following is my program to solve this box stacking problem. (I wrote my solution before looking at theirs, which appears to use bottom-up DP instead of top-down/memoization. Thus, I don't think I can cross-apply their time complexity to my algorithm.)

Below is the pseudo-code for my solution. Assume that putting something on the memo and checking the memo can be done in constant time.

Let a box have parameters width (w), height (h), and depth (d)
reward(maxW, maxD, elementH): 
 Zero max1, max2, max3
 If memo contains key (maxW, maxD), return associated value.
 for each box B in the list of input boxes:
 //If the box fits in any orientation, put it on the pile and recurse
 if (B.w < maxW AND B.d < maxD) OR (B.w < maxD AND B.d < maxW)):
 max1 = max(max1, reward(B.w, B.d, B.h) + B.h)
 if (B.h < maxW AND B.d < maxD) OR (B.h < maxD AND B.d < maxW)):
 max2 = max(max2, reward(B.h, B.d, B.w) + B.w)
 if (B.h < maxW AND B.w < maxD) OR (B.h < maxD AND B.w < maxW)):
 max3 = max(max3, reward(B.h, B.w, B.d) + B.d)
 put (maxW, maxD) onto memo, associated with max(max1, max2, max3)
 return max(max1, max2, max3)

• D.W.: Convert it to an iterative solution, then use the techniques you know (see cs.stackexchange.com/q/192/755). Or count the number of subproblems that will be solved.
• Raphael: The core consideration (usually) is, how many accesses to memo do you have to make? (another reference question)

Answer 1

A general trick that works for a lot of DP problems is to look at the parameters in your recursion -- the run time is then $O(n \times max(parameter_1) \times \dots \times max(parameter_k))$ where $n$ is the number of iterations (or, the number of inputs).

Consider for example a DP to solve the subset sum -- the recursion is given by $Q(i,s) := MIN(Q(i − 1,s), Q(i − 1,s − x_i)) $ where 0ドル \leq s \leq T$ and $T$ is the target sum.

The run time is then $O(n \times max(s)) = O(nT)$. And of course, this trick works with memoization only. If you have not done memoization, it is truly exponential (not pseudo-polynomial).

Why does this work? In each iteration $i,ドル we have to look at at-most $T$ different sub-problems (post memoization) before we hit the base case.