A proposed method to multiply two n-digit numbers breaks each of the numbers int
ID: 3683904 • Letter: A
Question
A proposed method to multiply two n-digit numbers breaks each of the numbers into 3 equal-length parts, does some linear-time calculations, computes 7 products of n/3-digit numbers, and then finishes up with some linear-time calculations that compute the actual desired product. What is the running time of the implied recursive algorithm? Give a recursive expression for the running time T(n), and solve the recurrence. Is this running time better than the running time of the Gauss's algorithm for multiplying complex numbers with only three multiplications?
Explanation / Answer
Multiplication algorithm: Recurrence relation
T(n) = 3T(n/2) + n
There are 3 ^i nodes at depth i, each with value n/2^ i , so the level-by-level sum () is an increasing
geometric series: T(n) = sigma (3/2)^ i *n.(where i=0 to L).
This geometric series is dominated by its final term (3/2) ^L*n.
Each leaf contributes 1 to this term; thus, the final term is equal to the number of leaves in the tree!
The recursion tree has L = log2 n levels, and therefore 3log2 n = n log2 3 leaves,
so T(n) = (n log2 3 ).
• T(n) = 2T(n/2) + n/ logn
The sum of all the nodes in the ith level is n/(log n i).
This implies that the depth of the tree is at most log n 1.
The level sums are neither constant nor a geometric series, so we just have to evaluate the overall sum
directly.
Recall (or if you’re seeing this for the first time: Behold!) that the nth harmonic number
Hn is the sum of the reciprocals of the first n positive integers: Hn =sigma(1/i) where i=1 to n.
It’s not hard to show that Hn = (log n);
in fact, we have the stronger inequalities ln(n + 1) Hn ln n + 1.
T(n) = (n/logn-i)(where i=0 to logn-1)=sigma(n/j)(where j=1 to log n)=n*Hlogn=theta(n log log n).
• T(n) = 4T(n/2) + n logn
There are 4 i nodes at each level i,
each with value (n/2 ^i )log(n/2 i ) = (n/2 i )(log n i); again, the depth of the tree is at most log n 1.
We have the following summation: T(n) =sigma n*2^i(logn-i)(where i=0 to log n-1).
We can simplify this sum by substituting j = lg n i:
T(n) = sigma n*2^logn-j*j(where j=I to log n) =sigma n^2 *j/2^j(where j=I to log n)= ( j ^2 )
Although this is not quite a geometric series, it is still dominated by its largest term.
Multiplication algorithm: Recurrence relation
T(n) = 3T(n/2) + n
There are 3 ^i nodes at depth i, each with value n/2^ i , so the level-by-level sum () is an increasing
geometric series: T(n) = sigma (3/2)^ i *n.(where i=0 to L).
This geometric series is dominated by its final term (3/2) ^L*n.
Each leaf contributes 1 to this term; thus, the final term is equal to the number of leaves in the tree!
The recursion tree has L = log2 n levels, and therefore 3log2 n = n log2 3 leaves,
so T(n) = (n log2 3 ).
• T(n) = 2T(n/2) + n/ logn
The sum of all the nodes in the ith level is n/(log n i).
This implies that the depth of the tree is at most log n 1.
The level sums are neither constant nor a geometric series, so we just have to evaluate the overall sum
directly.
Recall (or if you’re seeing this for the first time: Behold!) that the nth harmonic number
Hn is the sum of the reciprocals of the first n positive integers: Hn =sigma(1/i) where i=1 to n.
It’s not hard to show that Hn = (log n);
in fact, we have the stronger inequalities ln(n + 1) Hn ln n + 1.
T(n) = (n/logn-i)(where i=0 to logn-1)=sigma(n/j)(where j=1 to log n)=n*Hlogn=theta(n log log n).
• T(n) = 4T(n/2) + n logn
There are 4 i nodes at each level i,
each with value (n/2 ^i )log(n/2 i ) = (n/2 i )(log n i); again, the depth of the tree is at most log n 1.
We have the following summation: T(n) =sigma n*2^i(logn-i)(where i=0 to log n-1).
We can simplify this sum by substituting j = lg n i:
T(n) = sigma n*2^logn-j*j(where j=I to log n) =sigma n^2 *j/2^j(where j=I to log n)= ( j ^2 )
Although this is not quite a geometric series, it is still dominated by its largest term.
No, running time of the above method is not better than the running time of the Gauss's algorithm
because the above method is used for normal multiply of two numbers where as guass method is very useful for multiplying of complex numbers.