-
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?
-
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;
}
-
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)
;