Difference between revisions of "TADM2E 2.37"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Replaced content with "Th")
Line 1: Line 1:
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).
+
Th
 
 
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).
 

Revision as of 01:59, 14 July 2020

Th