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
- Since the method is being called three times, the complexity is going to be $3C(n/2) + n/2$.
My questions
What do they mean by hi-lo order bits?
How can I use a recurrence relation on this if I don't know how each recursion works?