Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 3 / ii

Split two $2^{k+1}$-digit numbers into high and low halves:where $B$ is the base raised to $2^k$. Their product isThe Karatsuba multiplication identitycomputes the three required half-size products $ab$, $cd$, and $(a+c)(b+d)$, soSince $f(0)=1$, induction gives $f(k)\le 3^k$. For $n=2^k$,Padding an arbitrary input length to the next power of two changes only the constant, yielding $O(n^{\alpha })$ digit multiplications with $\alpha =\log 3/\log 2$.