What is the time complexity of this dynamic programming algorithm?

Question

I'm learning dynamic programming solutions from a book. I understand the solution to a question, but I'm not sure of the time complexity of the solution which, the book didn't provide.

My question:

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), write code to calculate the number of ways of representing n cents.

My analysis:

Every input must go through 4 "levels", which is 25, 10, 5,1. In the first level the loop will execute n/25 time, in the second level the loop will execute at most (n/25)(n/10) times, the third executes at most (n/25)(n/10)(n/5), the last level executes at most(n/25)(n/10)*(n/5)n. So the total running time is (n/25)(n/10)*(n/5)n +(n/25)(n/10)(n/5)+(n/25)(n/10)+n/25 , which is O(N^4). First I'm not sure if my induction is right. Second, if I'm right, I wonder if there's a tighter bond since in each level I only calculated the max times instead of the average times.

The solution is below:

int makeChange(int n) {
    int[] denoms = {25, 10, 5, l};
    int[][] map = new int[n + l][denoms.length]; // precomputed 
            vals
    return makeChange(n, denoms, 0, map);
}

int makeChange(int amount, int[] denoms, int index, int[][] map) {
    if (map[amount][index] > 0) {//retrieve value
        return map[amount][index];
     }
    if (index >= denoms.length - 1) return 1; // one denom remaining
    int denomAmount denoms[index];
    int ways = 0;
    for (int i= 0; i * denomAmount <= amount; i++) {
        //go to next denom, assuming i coins of denomAmount
        int amountRemaining = amount - i * denomAmount;
        ways += makeChange(amountRemaining, denoms, index + 1, 
             map);
    }
    map[amount][index] = ways;
    return ways;
}

Answer 1

The algorithm as written is O(n²). When you analyze recursive functions, you can separate them into two pieces:

1. The work done by each function
2. The amount of times that work is done

Then it's just a matter of multiplying those two numbers together. Because the function results are being cached here, the work for each value in the cache is going to be done at most once. Since the cache is O(n) in size, it takes O(n) time to fill.

For the work done in each function, there is a while loop that goes through O(n) iterations. Multiplying these together gives you an estimate of O(n²), which is born out by doing a crude estimate (doubling the input value results in roughly quadrupling the time taken).