[Solved]: Complexity of a recursive bignum multiplication algorithm

Problem Detail: 

We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little.

The exercise

Consider the problem of multiplying two big integers, i.e. integers represented by a large number of bits that cannot be handled directly by the ALU of a single CPU. This type of multiplication has applications in data security where big integers are used in encryption schemes. The elementary-school algorithm for multiplying two n-bit integers has a complexity of . To improve this complexity, let x and y be the two n-bit integers, and use the following algorithm

Recursive-Multiply(x,y)   Write  x = x1 * 2^(n/2)+x0  //x1 and x0 are high order and low order n/2 bits        y = y1 * 2^(n/2)+y0//y1 and y0  are high order and low order n/2 bits   Compute x1+x0  and y1+y0   p = Recursive-Multiply (x1+x0,y1+y0)   x1y1 = Recursive-Multiply (x1,y1)   x0y0 = Recursive-Multiply (x0,y0)   Return  x1y1*2^n + (p-x1y1-x0y0)*2^(n/2)+x0y0 

(a) Explain how the above algorithm works and provides the correct answer.

(b) Write a recurrence relation for the number of basic operations for the above algorithm.

(c) Solve the recurrence relation and show that its complexity is $O(n^{\lg 3})$

My conjecture

1. Since the method is being called three times, the complexity is going to be $3C(n/2) + n/2$.

My questions

1. What do they mean by hi-lo order bits?

2. How can I use a recurrence relation on this if I don't know how each recursion works?

Asked By : Julio Garcia

Answered By : Yuval Filmus

The idea is to divide each $n$-bit integer into two halves of $n/2$ bits. For example, $10100010$ would be divided into $1010$ and $0010$. Naively, we would need to multiply four such halves, but in fact there is a way to do with only three. (This is similar to matrix multiplication algorithms such as Strassen's.) The algorithm described by the exercise is known as Karatsuba multiplication.

Regarding your other question, once you have reduced the computation of running time to a recurrence relation, you no longer need to understand anything more about the recursion in order to compute the running time - this is the main point of this abstraction.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14685