Content deleted Content added
Reverting edit(s) by 2605:A601:AA92:3800:94EA:49D9:5F2B:C10B (talk) to rev. 1161947574 by ClueBot NG: needs citation, may not be due mention (and if so should be better incorporated into existing prose) (UV 0.1.4) |
AksharVarma (talk | contribs) m →Time complexity analysis: fix typo t -> T |
||
Line 98:
Since one can extend any inputs with zero digits until their length is a power of two, it follows that the number of elementary multiplications, for any ''n'', is at most <math>3^{ \lceil\log_2 n \rceil} \leq 3 n^{\log_2 3}\,\!</math>.
Since the additions, subtractions, and digit shifts (multiplications by powers of ''B'') in Karatsuba's basic step take time proportional to ''n'', their cost becomes negligible as ''n'' increases. More precisely, if ''
:<math>T(n) = 3 T(\lceil n/2\rceil) + cn + d</math>
| |||