2. We can multiply large integers recursively by splitting each integer into thirds (rather than halves as done in class). 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 aan, where a is a constant, for the time to do all of the additions at each invocation of the routine. (C) Solve the recurrence using the tree method. Assume n is a power of three. Show your work. (d) How does the asymptotic running time of this algorithm compare to the previous version with time (ng3)? 2. We can multiply large integers recursively by splitting each integer into thirds (rather than halves as done in class). 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 aan, where a is a constant, for the time to do all of the additions at each invocation of the routine. (C) Solve the recurrence using the tree method. Assume n is a power of three. Show your work. (d) How does the asymptotic running time of this algorithm compare to the previous version with time (ng3)