Consider the integer multiplication problem.

Input: Two n$-$digit numbers, a and b$.$

Output: Product of a and b$.$

For example,

$1986=$ a

x $2020=$ b

$---------$

$0000$

$3972$

$0000$

$+3972$

$---------$

$4011720=$ a x b

This is the algorithm you learned in elementary school. Notice it takes O$($n$^2)$ time.

A divide$-$and$-$conquer solution to solve this problem is: We divide each integer into their left and right halves, which are n$/2$ digits long.

For example, a $=1986,$ b $=2020$

aL $=19|86=$ aR

bL $=20|20=$ bR

Then the product of a and b can then be obtained as:

aL aR

x bL bR

$-----------------------------$

aL bR aR bR

$+$ aL bL aR bL

$-----------------------------$

aL bL aL bR $+$ aR bL aR bR

So our algorithm is to compute four n$/2-$digit multiplications aL bL$,$ aL bR$,$ aR bL$,$ and aR bR$,$ and add.

Algorithm Divide$-$Mult$($a$,$b$)$:

if a or b has one digit, then:

return a $*$ b$.$

else:

Let n be the number of digits in max a$,$ b$.$

Let aL and aR be left and right halves of a$.$

Let bL and bR be left and right halves of b$.$

Let x$1$ hold Divide$-$Mult$($aL$,$ bL$).$

Let x$2$ hold Divide$-$Mult$($aL$,$ bR$).$

Let x$3$ hold Divide$-$Mult$($aR$,$ bL$).$

Let x$4$ hold Divide$-$Mult$($aR$,$ bR$).$

return x$1*10$n $+($x$2+$ x$3)*10$n$/2+$ x$4.$

end of if

Analyze the code and provide a "Big$-$O$"$ estimate of its running time in terms of n$.$

What is the recurrence equation of the time complexity?

What is the time complexity of the above divide$-$and$-$conquer algorithm?

O$()$