We can multiply large integers recursively by splitting each integer into thirds. In order to multiply the two three-digit numbers abc and def the standard algorithm would do nine atomic multiplications.

(a) Explain how you can do fewer atomic multiplications by forming the product (a + b + c)(d + e + f). How many atomic multipications do you use?

(b) Write a recurrence for how fast this version of integer multiplication is. In order to keep this simple, just use an, where a is a constant, for the time to do all of the additions at each invocation of the routine. Assume n is a power of three