TADM2E 2.38

From Algorithm Wiki
Revision as of 12:57, 30 January 2017 by Bluefog (talk | contribs) (Correct complexity analysis)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, 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, $ O(n^2) $