Problem 2. Karatsuba algorithm for integer multiplication has a runtime complexity of O(n1.58) We want to test a few multiplication algorithms along the lines of Karatsuba. You may use s for an atomic multiplication and for an atomic addition, wherever required. Please follow and answer the following questions: 1. Write a simple (without any clever tricks) recurrence equation for a multiplication algo- rithm that divides each n digit number into 3 parts rather than 2 parts with the size of each part being z. We will call this TC algorithm 2. Solve the recurrence equation for TC algorithm using the recursion tree approach as shown in class 3. For this and the rest of the parts we will only find the Big-O runtime. What is the runtime of TC algorithm? 4. You probably noticed that TC algorithm is slower than Karatsuba's algorithm. We will try to make it faster. While still splitting the integers into three parts, we will reduce the number of multiplications for TC algorithm by 1. What is the runtime of this algorithm with this modification? 5. What should be the number of multiplications (keep the 3 part split), so that TC algorithm becomes faster than Karatsuba algorithm? What is the runtime!? 6. Now we will divide each n-digit number into 4 parts, rather than 3, with the size of each part being 4. How many multiplications do we need so that the runtime of this new algorithm is faster than Karatsuba algorithm? For each part, show your work. Problem 2. Karatsuba algorithm for integer multiplication has a runtime complexity of O(n1.58) We want to test a few multiplication algorithms along the lines of Karatsuba. You may use s for an atomic multiplication and for an atomic addition, wherever required. Please follow and answer the following questions: 1. Write a simple (without any clever tricks) recurrence equation for a multiplication algo- rithm that divides each n digit number into 3 parts rather than 2 parts with the size of each part being z. We will call this TC algorithm 2. Solve the recurrence equation for TC algorithm using the recursion tree approach as shown in class 3. For this and the rest of the parts we will only find the Big-O runtime. What is the runtime of TC algorithm? 4. You probably noticed that TC algorithm is slower than Karatsuba's algorithm. We will try to make it faster. While still splitting the integers into three parts, we will reduce the number of multiplications for TC algorithm by 1. What is the runtime of this algorithm with this modification? 5. What should be the number of multiplications (keep the 3 part split), so that TC algorithm becomes faster than Karatsuba algorithm? What is the runtime!? 6. Now we will divide each n-digit number into 4 parts, rather than 3, with the size of each part being 4. How many multiplications do we need so that the runtime of this new algorithm is faster than Karatsuba algorithm? For each part, show your work