Problem Detail: 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)
Asked By : apnorton
Answered By : RDN
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10369
