# Time Complexity Upper Bound of Memoized DP Problems

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.)

import java.util.*;

public class BoxStack {
private static HashMap<Base, Double> memo; //My memo

//How many times do I call the reward subroutine *and* look something up?
private static int callCt = 0;

//Test data
private static double[] h = {4, 1, 4, 10}; //heights of boxes
private static double[] w = {6, 2, 5, 12}; //widths of boxes
private static double[] d = {7, 3, 6, 32}; //depths of boxes
private static final int N = 4;            //number of test cases

//My "r()" subroutine (short for reward).
//Given a box size (maximum width, maximum depth, and height of the box to be added)
//Return the maximum size tower I can place on top of that base
public static double r(double maxW, double maxD, double elementH) {
//I don't really need 3 max variables here, but it helped me to think
//about the maximum of each box with a given rotation
double max1 = 0;
double max2 = 0;
double max3 = 0;

//Return the memoized result if possible
Base testBase = new Base(maxW, maxD);
if (memo.get(testBase) != null) {
return memo.get(testBase);
}

//We're going to do some calculating, so increment call count
callCt++;

//Go through all the boxes...
for (int i = 0; i < N; i++) {
//If you can stack it on top of the base in any orientation, do so!
if ((w[i] < maxW && d[i] < maxD) || (w[i] < maxD && d[i] < maxW)) {
max1 = Math.max(max1, r(w[i], d[i], h[i])+h[i]); //Recursive call!
}

if ((h[i] < maxW && d[i] < maxD) || (h[i] < maxD && d[i] < maxW)) {
max2 = Math.max(max2, r(h[i], d[i], w[i])+w[i]);
}

if ((h[i] < maxW && w[i] < maxD) || (h[i] < maxD && w[i] < maxW)) {
max3 = Math.max(max3, r(h[i], w[i], d[i])+d[i]);
}
}

memo.put(testBase, Math.max(max1, Math.max(max2, max3)));

return Math.max(max1, Math.max(max2, max3));
}

public static void main(String[] args) {
//Set up memo
memo = new HashMap<Base, Double>();

//Print max height
System.out.println(r(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0));

System.out.println(callCt);
}

//Something I can use to map my base sizes to my heights
private static class Base {
double width;
double height;

public Base (double width, double height) {
this.width = width;
this.height = height;
}

@Override
public boolean equals(Object o) {
Base that = (Base) o;
return ((that.width == this.width && that.height == this.height) || (that.height == this.width && that.width == this.height));
}

@Override
public int hashCode() {
return (this.toString()).hashCode();
}

public String toString() {
return ("(" + Math.min(width, height) + "," + Math.max(height, width) + ")");
}
}
}

-

## migrated from stackoverflow.comMar 7 '13 at 16:47

This question came from our site for professional and enthusiast programmers.

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.

-