Question

Show that the greedy algorithm for making change for n cents using quarters, dimes, nickels, and pennies hasO(n)complexity measured in terms of comparisons needed.

Short answer

The result is proved.

Step-by-step solution

Algorithm

Greedy algorithm

Procedure- change

$(c_1,c_2,...,c_r:valuesofdenominationsofcoins,where{c}_1>c_2>...>c_r;n:apositiveinteger)$.

$\begin{array}{r}\text{for}i:=1\text{to}r\\ {\mathrm{d}}_i:=0\\ \text{while}n\ge c_i\\ d_i:=d_j+1\\ n:=n-c_i\end{array}$

Solution

The algorithm makes 1 comparison in each iteration of the while-loop $(n\ge c_i)$.

Since i can take on the values from 1 to r (for $i:=1tor$), i can take on r values and thus there are at most r iterations of the for-loop.

In worst-case scenario, the while-loop iterates n times (when the change consists of only cents).

The number of comparisons is then the product of the number of comparisons per iteration and the number of iterations (Note: product since the loops are nested).

Number of comparisons $=1\cdot r\cdot n=rn$

Thus at most rn comparisons are made (with r a constant) and rn is O(n) where r is a constant.