Consider the following recursive algorithm: procedure LongIntegerMultiply(X, Y, n: X and Y are n-bit integers, n is a power of 2) if n = 1 then return X*Y/* line 1: single-bit multiplication */else split X into X_1, X_2 and Y into Y_1, Y_2 such that X = 2^n/2 X_1 + X_2 and Y = 2^n/2Y_1 + Y_2 U leftarrow LongIntegerMultiply (X_1, Y_1, n/2) V leftarrow LongIntegerMultiply (X_2, Y_2, n/2) W rightarrow LongIntegerMultiply (X_1 - X_2, Y_1 - Y_2, n/2) Z leftarrow U + V - W return 2^nU + 2^n/2Z + V A. Set up a divide-and-conquer recurrence relation for the number of single-bit multiplications (done in line 1) required to compute the product of two n-bit integers X and Y, where n is a power of 2 (i.e. n = 2^k for some integer k), using the algorithm above. B. Use the recurrence relation above and the Master theorem to derive a big-O estimate for the number of single-bit multiplications used in the algorithm above