我不确定是否可以在此站点上发布此类问题，但我想知道您是否可以帮助我解决一直困扰我的问题。

我们已经开始学习递归算法的分析，我掌握了它的要点。但是有一些问题，比如我要发布的问题，这让我有点困惑。你能帮我么？

感谢您的时间。

题：

考虑两个大整数相乘的问题，即由单个 CPU 的 ALU 无法直接处理的大量位表示的整数。这种类型的乘法在加密方案中使用大整数的数据安全中具有应用。用于将两个 n 位整数相乘的小学算法的复杂度为 . 为了提高这种复杂度，让 x 和 y 为两个 n 位整数，并使用以下算法

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) 解释上述算法的工作原理并给出正确答案。

(b) 写出上述算法基本运算次数的递推关系。

(c)求解递推关系，证明其复杂度为O(n^lg3)