Let X $=$ x$1$ x$2$

$...$ xn and Y $=$ y$1$ y$2$

$...$ yn be two n$-$digit integers. Design a divide and conquer

algorithm that returns the multiplication of X and Y $.$ Hint: Assume that n is a power of $2.$

$($a$)$ Specify the input.

$($b$)$ Specify the output.

$($c$)$ Explain the running time if n $=1.$

$($d$)$ Explain the Divide step.

$($e$)$ Explain the Conquer step.

$($f$)$ Explain the Combine step.

$($g$)$ Write the recurrence for the running time function T$($n$)$ and solve it$.$