search

jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.92k stars 1.02k forks source link

The formula is incorrect #101

Closed wuloop closed 5 years ago

wuloop commented 5 years ago

Please verify that the error is present in the most recent revision before reporting.

Chapter number or note title: 00-intro

Page number: [page] Page number 4

Error description:
The K in the formula z=x*y should be 0 to **m+n-2, because max(i) is m-1 and max(j) is n-1**.

Suggested fix (if any): [fix] The K in the formula z=x*y should be 0 to **m+n-2.

Zacharyzqc commented 5 years ago

I have the same opinion

jeffgerickson commented 5 years ago

You forgot about carries. Consider 999 * 999 = 998001. Here m = n = 3, and the product has m+n = 6 digits.