# Complexity of a recursive bignum multiplication algorithm

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?

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.
• Well, $n/2$ has no meaning, since you don't know how much each operation actually costs - instead, you want $O(n)$. Other than that, it looks fine. – Yuval Filmus Sep 30 '13 at 0:43
• Take $f(n) = cn + d$ and use $f(n) = \Theta(n)$. – Yuval Filmus Sep 30 '13 at 5:44
• You should understand what $\Theta(n)$ means. That's more important than what you professor used, and could help you answer your own question. – Yuval Filmus Oct 1 '13 at 6:59