Karatsuba multiplies two n-digit numbers with three half-size multiplications instead of four. Solve its recurrence exactly, and compute how many digit multiplications it uses for n = 1024 against the schoolbook method.

Karatsuba multiplies two n-digit numbers with three half-size multiplications instead of four. Solve its recurrence exactly, and compute how many digit multiplications it uses for n = 1024 against the schoolbook method.

Approach: Write the recurrence with the three recursive calls and linear combining work, apply the master theorem, then evaluate the leaf count at the stated size.

59049 against 1048576, a factor of about 17.8. Karatsuba writes each number as a * B + b with B the half-size base and computes ab, cd and (a+b)(c+d), recovering the middle term by subtraction, so T(n) = 3T(n/2) + O(n). The master theorem gives n^{log_2 3} = n^{1.585}, and since the driving term n is polynomially smaller than n^{1.585} the first case applies and T(n) = Theta(n^{log_2 3}). At n = 1024 the recursion depth is 10, so the number of single digit multiplications at the leaves is 3^10 = 59049, while the schoolbook method performs 1024^2 = 1048576. The gain is partly given back by the additions and subtractions at every level, so the crossover point in practice sits at a few hundred to a thousand bits, below which schoolbook is faster because its inner loop is a tight sequence of machine multiply-accumulate instructions with no recursion overhead.

Follow-up: What exponent does the Toom-3 split achieve and why is it still slower than the transform based method for very large inputs?

Key concepts: karatsuba, master theorem, recursion depth, crossover point.