In class, we described and analyzed Karatsuba's algorithm for long integer multiplication. It turns out the Karatsuba algorithm is a special case of the Toom-Cook multiplication that splits the integers into k pieces.Toom3 is a very common approach, in Toom-3 integers A and B are each split into 3-parts. Below is a description of Toom-3: - Given two integers A and B, split into A3,A2,A1 and B3,B2,B1, with A3 and B3 being the most significant chunks -leftmost bits-. - Calculate the following intermediate values: X=A1B1Y=(A3+A2+A1)(B3+B2+B1)Z=(A3A2+A1)(B3B2+B1)U=(4A32A2+A1)(4B32B2+B1)V=A3B3 - find C1,C2,C3,C4,C5 using: C1=XC5=VC3=(Y+Z)/2XVC4=(3C1+6C3+18+C5VY)/6C2=YC1C3C4C5 - The result C is the concatenation of C1,C2,C3,C4,C5 You can assume that all addition, subtraction and division by a constant are (n). Answer the following questions: 1- Write down a recurrence T(n) describing the algorithm. (3 points) 2- Find the of Toom-3 using the Master Theorem. ( 2 points) 3- Draw the recursion tree for T(n)-showing three levels should be sufficient-. ( 3 points) 4- Find the formula describing the cost of layer k of the tree. ( 2 points) 5- What is the depth of the tree in terms of n. (2 points) 6- Find the of Toom-3 using the previous values -from the tree-. ( 2 points)