Due: Tuesday, Sep. 6. (This Tuesday is treated like a Monday.)
For simplicity in explanation, I will use the approximation that log2(3) is about 1.59.
Consider the problem of multiplying an n digit number by an m digit number, where m < n. The grade-school algorithm does the job in time O(nm). Our fast divide-and-conquer algorithm uses time O(n1.59), which is worse than the grade-school algorithms if m < n0.59.
Show how to improve the divide-and-conquer algorithm so that it takes time O(nm0.59). Explain how your algorithm works and argue that it meets the desired time requirement.
Hint. Use the divide-and-conquer algorithm as a black box. Build a hybrid between the grade-school algorithm and the divide-and-conquer algorithm.