Assume that we can find the product of two -digit-numbers using some number of multi-plications of 3-digit numbers (plus some additions, subtractions and shifts). What is the largest number of 3-digit number multiplications that leads to an asymptotically faster algorithm than the 2 divide-and-conquer algorithm discussed in the lecture? Provide and solve the recurrence equations.

Provide pseudocode for this algorithm. (don't suggest the copied code from somewhere, only pseudocode with explanation)