Karatsuba Multiplication Runs in \(\Theta(n^{\log_2 3})\) Time
Statement
Karatsuba’s algorithm multiplies two \(n\)-digit integers using \(T(n)\) digit operations, where \[ T(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585}). \] This is asymptotically faster than the schoolbook \(\Theta(n^2)\) algorithm (Karatsuba and Ofman 1963; Kleinberg and Tardos 2005).
Recurrence
Karatsuba splits each \(n\)-digit operand into two \(n/2\)-digit halves: \[ X = X_1 \cdot B^{n/2} + X_0, \qquad Y = Y_1 \cdot B^{n/2} + Y_0. \] The trick is the identity \[ X_1 Y_0 + X_0 Y_1 = (X_1 + X_0)(Y_1 + Y_0) - X_1 Y_1 - X_0 Y_0, \] which reduces the number of \(n/2\)-digit multiplications from four to three. The remaining work — additions, subtractions, and shifts — is \(\Theta(n)\).
So \(T(n)\) satisfies \[ T(n) = 3 \, T(n/2) + \Theta(n), \qquad T(1) = \Theta(1). \]
Two technicalities
Sums of half-digit numbers can carry. \(X_1 + X_0\) and \(Y_1 + Y_0\) are at most \((n/2 + 1)\)-digit numbers, not \(n/2\)-digit. The size grows by one bit per recursive level, contributing a multiplicative constant — absorbed into the \(\Theta(n)\) overhead — but not changing the recursion structure.
Floors and ceilings. When \(n\) is odd, the split is \(\lceil n/2 \rceil\) and \(\lfloor n/2 \rfloor\). Standard padding arguments show this does not affect the asymptotic bound.
Solving the recurrence via the master theorem
Match \(T(n) = a \, T(n/b) + f(n)\) with \(a = 3\), \(b = 2\), \(f(n) = \Theta(n)\).
The critical exponent is \(\alpha = \log_b a = \log_2 3 \approx 1.585\).
Compare \(f(n) = \Theta(n^1)\) to \(n^\alpha = n^{1.585}\): \[ f(n) = O(n^{\alpha - \epsilon}) \quad \text{for any } \epsilon < \alpha - 1 \approx 0.585. \]
So Case 1 of the master theorem applies, giving \[ T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 3}). \]
Direct recursion-tree argument
For an explicit picture: at depth \(i\) in the recursion tree there are \(3^i\) subproblems each of size \(n / 2^i\), contributing \(3^i \cdot \Theta(n / 2^i) = \Theta(n \cdot (3/2)^i)\) work at level \(i\). Summing over \(i = 0, \dots, \log_2 n - 1\): \[ \sum_{i=0}^{\log_2 n - 1} n \cdot (3/2)^i = \Theta\left( n \cdot (3/2)^{\log_2 n} \right) = \Theta(n \cdot n^{\log_2 (3/2)}) = \Theta(n^{1 + \log_2 3 - 1}) = \Theta(n^{\log_2 3}). \]
The leaves contribute \(3^{\log_2 n} = n^{\log_2 3}\) constant-cost subproblems, matching the level-by-level total. Both halves of the bound agree at \(\Theta(n^{\log_2 3})\).
Tightness
The lower bound \(T(n) = \Omega(n^{\log_2 3})\) comes from the leaves alone: the recursion has \(n^{\log_2 3}\) leaves, each requiring \(\Omega(1)\) work. So Karatsuba’s complexity is exactly \(\Theta(n^{\log_2 3})\).
Comparison
| Algorithm | Recurrence | Complexity |
|---|---|---|
| Schoolbook | \(T(n) = 4 T(n/2) + \Theta(n)\) | \(\Theta(n^2)\) |
| Karatsuba | \(T(n) = 3 T(n/2) + \Theta(n)\) | \(\Theta(n^{1.585})\) |
| Toom-3 | \(T(n) = 5 T(n/3) + \Theta(n)\) | \(\Theta(n^{1.465})\) |
| Schönhage–Strassen | (FFT-based) | \(\Theta(n \log n \log \log n)\) |
| Harvey–van der Hoeven (2019) | (galactic) | \(\Theta(n \log n)\) |
The Karatsuba bound is the simplest and the first to break the \(\Theta(n^2)\) barrier; it remains the algorithm of choice for moderate \(n\) in libraries like GMP.