Problem 36E
Show that the greedy algorithm for making change for n cents using quarters, dimes, nickels, and pennies has O(n) complexity measured in terms of comparisons needed.
Step-by-Step Solution:
Step 1</p>
In this problem, we are asked to show that the greedy algorithm for making change for n cents has O(n) complexity measured in terms comparisons needed.
Step 2</p>
The algorithm for making changes for n cents using quarters, dimes, nickels and pennies are
Procedure change
for i=1 to n
di=0
while
{is the number of coins of denominations ci }
Step 3 of 3
