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.Question: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 algorithmRecursive-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)
Recursive-Multiply Analysis
algorithms