TADM2E 2.37 - Revision history

Matt: Undo revision 797 by EthanGamer (talk)

2020-07-23T13:35:11Z

Undo revision 797 by EthanGamer (talk)

EthanGamer: Replaced content with "Th"

2020-07-14T01:59:50Z

Replaced content with "Th"

Algowikiadmin: Recovering wiki

2014-09-11T18:24:10Z

Recovering wiki

New page

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).

← Older revision		Revision as of 01:59, 14 July 2020
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).~~

← Older revision		Revision as of 13:35, 23 July 2020
Line 1:		Line 1:
−	Th	+	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).