Nick

08-27-2001, 11:23 AM

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

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?

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

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?