Problem $5.$ Karatsuba multiplication reduces the time complexity of multiplying two n$-$ digit numbers to

O$($nlog$23)$ O$($n$1\mathrm{.}585),$ using the recurrence:

T $($n$)=3$T $($n$/2)+$ O$($n$)$

The algorithm splits the numbers as follows:

x $=$ x$110$n$/2+$ x$0,$ y $=$ y$110$n$/2+$ y$0$

and computes three products: x$0$ y$0,$ x$1$ y$1,$ and $($x$0+$ x$1)$ cdot$($y$0+$ y$1).$ Two values you are multiplying

might be n$/2+1$ digits each, rather than n$/2$ digits, since the addition might have led to a carry. For

instance compute $($x$1+$ x$0)($y$1+$ y$0)$ for x $=53$ and y $=52.$ Notice the carry and the extra digit. So the

recurrence will be

T $($n$)=2$T $($n$/2)+$ T $($n$/2+1)+$ O$($n$)$

Prove that this issue won$$t affect our analysis and we still O$($nlog$23)$ complexity.