2.43

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

X=n-digit number (abcdefghijklmn), y= n-digit number (ABCDEFGHIJKLMN) say

X * y = X * N + X * M0 + X * L00 + X * K000 + .... + X * B000000000000 + X * A0000000000000

With each multiple consisting of further digit by digit multiplications as

X * N = n * N + m0 * M + l00 * L + k000 * K + .... + b000000000000 * B + a0000000000000 * A

i.e. n multiples, each generated with n digit by digit multiplications and additions hence, [math]\displaystyle{ O(n^2) }[/math]

Back to Chapter 2