Consider an algorithm for integer multiplication of two -digit numbers where each number is split into three parts, each with digits.

(a) Design and explain such an algorithm, similar to the integer multiplication algorithm presented in class. Your algorithm should describe how to multiply the two integers using only six multiplications on the smaller parts (instead of the straightforward nine).

(b) Determine the asymptotic running time of your algorithm. Would you rather split it into two parts or three parts?

(c) Suppose you could use only five multiplications instead of six. Then determine the asymptotic running time of such an algorithm. In this case, would you rather split it into two parts or three parts?

Transcribed image text