I need help with question 5b. I understand how the algorithm works but I do not
ID: 3143555 • Letter: I
Question
I need help with question 5b. I understand how the algorithm works but I do not understand how to find the value of N that would create the worst-case scenario. The answer key says that the worst-case number of comparisons is 20 at N = 94, but I do not understand how they got to those numbers.
5. Consider Algorithm 5.8 for making change. Let 1 s N 100. (a) What is the best-case number of 2 comparisons? For what N does this occur? Justify your answer. (b) What is the worst-case number of 2 comparisons? For what N does this occur? Justify your answer.Explanation / Answer
The alogrithm starts with T = 0
then it moves to either one of the following -
First iteration
1. T = 25 if N >= 25 {no of comparison in this first round : 1)
2. T = 10 if 25>N >=10 {no of comparison in this first round : 2)
3. T = 5 if 10> N >=5 {no of comparison in this first round : 3)
4. T = 1 if 4 >N >=1 {no of comparison in this first round : 3)
Notice here that any number greater than 25 will first have to go through the first type of comparison and then in the next iteration would go through the additional other type of comparison.
So from here we can easily say that worst case N has to be greater than 25.
Similarly if you see here, that if the N >75, it will have to travel additional iterations compared to N<75, because of the additional comparison of type 1 following by other type of comparison in next iterations.
so we know the worst case has to be greater than >75 (2x1 = 3 comparisons)
here adding (10+10) bring another 6 comparisons from type 2. But more comparison will happen if after first 10, it moves down to type 3. so lets add (10+9), in this case no of comparison would be (2+3+3x3)
N = 94
in bracket comparison and outside that iteration value of T is mentioned.
T = {0, (1)25, (1)50, (1)75, (2)85, (3)90, (3)91, (3)92, (3)93, (3)94}
.While for 95, just (2x3+3x2) = 12.
for 96, (2x3+3x2+4) = 16