Karatsuba’s algorithm multiplies two n-bit integers by recursively computing three (3) pairwise products of n 2 -bit int

[answerhappygod]

Karatsuba’s algorithm multiplies two n-bit integers by
recursively computing three (3) pairwise products of n 2 -bit
integers (see Lecture 2).
(a) [ 10 Points ] Show that the problem can be solved by
recursively computing six (6) pairwise products of n 3 -bit
integers. Analyze the running time of the algorithm.
(b) [ 40 Points ] Can you reduce the number of products of n 3
-bit integers required in part (a) to five (5)? If not, why? If
yes, describe the algorithm and analyze its running time.