Chapter number and Note title: Chapter 0
0.6 Analyzing algorithms
Running time
Page number: 16
Error description: The trailing constant in the recurrence for the time complexity of PeasantMultiply is not correct.
Suggested fix: In the paragraph before the last, the expression
T(x, y) <= T([x/2], 2y) + 2
should be replaced with
T(x, y) <= T([x/2], 2y) + 4
because at each iteration (or function call, in case of the recursive version) of PeasantMultiply, we perform the following tasks.
check if x is zero (an operation that we choose not to count here),
check the parity of x (one operation),
add y to product if x is odd (at most one operation),
compute half of x (one operation),
and add y to itself (one operation).
Therefore, at one iteration, we perform at most four operations. Analyzing the recursive formula for x times y given on page 16 yields the same result, too.
Obviously, this change in the trailing constant of the recurrence will not change the asymptotic upper bound which is T(x, y) = O(log x) anyway.
The error is present in the most recent revision.
Chapter number and Note title: Chapter 0 0.6 Analyzing algorithms Running time
Page number: 16
Error description: The trailing constant in the recurrence for the time complexity of PeasantMultiply is not correct.
Suggested fix: In the paragraph before the last, the expression
should be replaced with
because at each iteration (or function call, in case of the recursive version) of PeasantMultiply, we perform the following tasks.
Therefore, at one iteration, we perform at most four operations. Analyzing the recursive formula for x times y given on page 16 yields the same result, too.
Obviously, this change in the trailing constant of the recurrence will not change the asymptotic upper bound which is T(x, y) = O(log x) anyway.