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)