Difference between revisions of "TADM2E 2.37"
(Recovering wiki) 
(No difference)

Latest revision as of 18:24, 11 September 2014
The repeated addition method should be complexity O(b^n) in the worst case. If y is 5 digits long (worst case  99999), and we are working in base 10, we would expect to add x to itself around 10^5 (10000) times in the worst case. Note that this assumes adding two n digit numbers together is O(1).
If we consider how humans add by hand (i.e. add the digits in each place value together  single digit by single digit addition), the addition operation is actually an O(n) operation. Thus, this would make the repeated addition algorithm for multiplication O(n * b^n).
x= ndigit number, y = ndigit number
x + x = <ndigit number> + <ndigit nhumber> considering each digit has a carry, i.e. we do 2n  2 additions in worst case since the first digit cannot have a carry. Since we do it y1 times hence we do, (2n2) * (y  1) times. Maximum value of y = b^n.
Hence, we end up with (2n2) * (b^n 1). i,e, O(n * b ^n).