 Solution

A divide-and-conquer algorithm handles small base cases directly, divides a larger instance into smaller instances of the same problem, solves them recursively, and combines their answers. The savings come from the number and sizes of recursive calls and the combination cost.

For Karatsuba multiplication, split the $n$-bit inputs as $x=aB+b$, $y=cB+d$, where $B=2^k$ and $k=\lceil n/2\rceil$. Compute only three recursive products:Then the Karatsuba three-product identity givesThe absolute differences have at most $k$ bits; multiply their magnitudes and restore the sign of $r$. Additions, subtractions and shifts cost $O(n)$ bit operations. With constant-size base cases, the recurrence relation is $T(n)=3T(\lceil n/2\rceil )+O(n)$, giving $O(n^{{\log }_{2}3})$ by the Master theorem. The difference-product version avoids an extra carry bit in the recursive operands.