(20) Karatsuba's algorithm is a fast multiplication algorithm, which allows computing the product of two large numbers x and y using three multiplications of smaller numbers, each with half as many digits as x or y, plus some additions and digit shifts. In this question, we want to make a small change. The number of digits that each smaller number has is only one third of x or y. We will assume for this question that n is an integer power of 3. x = a 229 +6.25 +c Let x, y be two n-bit integers, and write . Then we have: y=d. 2*?"+e. 23 +f 2n { 2n -e 4n 4n 2n xy = ad 2*%+(ae+bd)2" +(af+be+cd)2*" +(6f+ce)2% +cf = A2*5* +B2" +C2*" +D2? +E, where A ad B ae + bd af + be + cd bf + ce cf D || | || E There are two Divide-and-Conquer based algorithms described as below. In Algorithm A, computing each value of ad, ae, af, bd, be, bf, cd, ce, cf can be regarded as a sub-problem. We first solve the sub-problems and then compute zy by merging the solutions of sub-problems to get A, B, C, D, E based on the equations above. In Algorithm B, we compute A, B, C, D, E by computing X0, X1, X2, X3, X4 below, where the multiplication in each of them is computed recursively: Xo = cf A= (6X0 4X1 + X2 4X3 + X4) X1 = (a +b+c)(d+e+f) B= (-2X1 + X2 + 2X3 X4) X2 = (4a + 2b + c)(4d + 2e + f) = C= 24 (-30X0 + 16X1 X2 + 16X3 X4) X3 = (a b+c)(d e+f) D= 12 (8X1 X2 8X3 + X4) X4 (4a 2b + c)(4d 2e +f) E = X For each algorithm A and B, write down the recurrence relation T(n) for the time complexity, and then compute T(n) explicitly. Which of the algorithms A and B runs asymptotically faster? How do they compare (asymptotically) to Karatsuba's Algorithm? = e Notes: (i) Dividing an n-bit integer by 3 can be done in O(n) time, if the dividend is known to be a multiple of 3, and you can assume this for this question. (ii) In 2 x In 5