I am not sure if I can post these kinds of questions on this site, but I was wondering if you could help me with a question that's been bothering me.
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. Can you please help me?
Thank you for your time.
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^lg3)