[Oops.] Time complexity of peasant multiplication

[pooyataher]

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

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.