Difference between revisions of "TADM2E 2.38"
From Algorithm Wiki
(Recovering wiki) |
(Correct complexity analysis) |
||
| Line 1: | Line 1: | ||
| − | X=n-digit number, y= n-digit number (ABCDEFGHIJKLMN) say | + | 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 | X * y = X * N + X * M0 + X * L00 + X * K000 + .... + X * B000000000000 + X * A0000000000000 | ||
| − | i.e. n multiples | + | 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>O(n^2)</math> | ||
Latest revision as of 12:57, 30 January 2017
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) $
