Karatsuba's algorithm for multiplying 2 n-bit numbers is described in Figure 1. Grade school-taught methods for multiplying two 2-digit numbers requires the multiplication of n2 single digit multiplications. The idea behind Karatsuba's algorithm is that y can be written as y 2(io+o2/2 +oyo, where z-#1 * nn/2 +ro and likewise for y. Although, a problem here is that computing this requires 4 multiplications of n/2 bit numbers (let this method be known as the naive method). With a simple arithmetic insight, though, we can first note that Now re-arranging equation, we can get Now, we can get xi* additions/subtractions) yo+o), o yo with just three n/2 bit multiplications (and some In this problem you will need to answer the following questions: 1. Using the substitution method (you cannot use the Master theorem) and the recurrence relation for Karatsuba's algorithm, prove the running time of Karatsuba's algorithm 2. Give the recurrence relation and show the running time of the naive method described above using the substitution method. Is this asymptotically more efficient than grade school-taught multiplication method? Karatsuba(x:n-2 bit number, y: n 2 bit number): if ns2 return xy r1,xo-top and botton n/2 bits of x y,yotop and bottom n/2 bits of y a Karatsuba (+o yyo) b = Karatsuba(zi, yi) cKaratsuba (o o) return a2" + (a-(b +c))2n/2 + C Figure 1: Karatsuba's algorithm: note , ro. Vi.yo are all n/2 bit numbers