Difference between revisions of "TADM2E 2.37"

Latest revision as of 13:35, 23 July 2020

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= n-digit number, y = n-digit number

x + x = <n-digit number> + <n-digit 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 y-1 times hence we do, (2n-2) * (y - 1) times. Maximum value of y = b^n.

Hence, we end up with (2n-2) * (b^n -1). i,e, O(n * b ^n).