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.