# Problem

• 08-27-2001
Nick
Problem
Ok here's a problem I asked following the demise of the old c board.

Given that you have a unlimited amount of pennies, nickles, dimes, quaters, halve dollars. To find all the ways that you can make change for a given amount one can write

Code:

``` int count_change(int amount) {     return cc(amount, 4); } int cc(int amount, int coin) {     static const int denom[] = {1, 5, 10, 25, 50};     if (amount == 0)         return 1;     else if (coin < 0 || amount < 0)         return 0;     return cc(amount - denom[coin], coin) + cc(amount, coin - 1); }```

My question is what is the order of growth (in Big Oh Notation) of the

number of steps? And show?
• 08-29-2001
Nick
No one tried!

Code:

``` // mimic recursive function int count_change(int amount) {     int i, j, k, m, n;     int c = 0;     for (i = amount; i > 0; i -= 50) {         for (j = i; j > 0; j -= 25) {             for (k = j; k > 0; k -= 10) {                 for (m = k; m > 0; m -= 5) {                     for (n = m; n > 0; n -= 1)                         ;                     if (n == 0)                         ++c;                 }                 if (m == 0)                     ++c;             }             if (k == 0)                 ++c;         }         if (j == 0)             ++c;     }     if (i == 0)         ++c;     return c; }```
• 08-29-2001
SilentStrike
So it's running time is O(N^4)?

I was messing with it a little, but couldn't do anything definitive.

BTW, what is this loop doing?

for (n = m; n > 0; n -= 1)

;