Strassen’s Algorithm Multiplies Matrices in \(\Theta(n^{\log_2 7})\) Time
Statement
Strassen’s algorithm multiplies two \(n \times n\) matrices in \(T(n)\) scalar operations, where \[ T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807}). \] This is asymptotically faster than the schoolbook \(\Theta(n^3)\) algorithm and was the first proof that matrix multiplication can be done in subcubic time (Strassen 1969; Cormen et al. 2009).
Recurrence
Partition each \(n \times n\) matrix into four \(n/2 \times n/2\) blocks. Strassen’s identities express the four \(n/2 \times n/2\) output blocks in terms of just seven \(n/2 \times n/2\) matrix products plus \(\Theta(n^2)\) scalar additions and subtractions for the \(\Theta(n^2)\)-element block combinations:
\[ \begin{aligned} M_1 &= (A_{11} + A_{22})(B_{11} + B_{22}) \\ M_2 &= (A_{21} + A_{22}) B_{11} \\ M_3 &= A_{11}(B_{12} - B_{22}) \\ M_4 &= A_{22}(B_{21} - B_{11}) \\ M_5 &= (A_{11} + A_{12}) B_{22} \\ M_6 &= (A_{21} - A_{11})(B_{11} + B_{12}) \\ M_7 &= (A_{12} - A_{22})(B_{21} + B_{22}) \end{aligned} \]
with output blocks \(C_{11} = M_1 + M_4 - M_5 + M_7\), \(C_{12} = M_3 + M_5\), \(C_{21} = M_2 + M_4\), \(C_{22} = M_1 - M_2 + M_3 + M_6\).
So \[ T(n) = 7 \, T(n/2) + \Theta(n^2), \qquad T(1) = \Theta(1). \]
Solving via the master theorem
Match \(T(n) = a T(n/b) + f(n)\) with \(a = 7\), \(b = 2\), \(f(n) = \Theta(n^2)\).
Critical exponent: \(\alpha = \log_b a = \log_2 7 \approx 2.807\).
Compare \(f(n) = \Theta(n^2)\) to \(n^\alpha = n^{2.807}\): \[ f(n) = O(n^{\alpha - \epsilon}) \quad \text{for any } \epsilon < \alpha - 2 \approx 0.807. \]
Case 1 of the master theorem applies: \[ T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 7}). \]
Recursion-tree picture
At depth \(i\) there are \(7^i\) subproblems each of size \(n/2^i\), and each contributes \(\Theta((n/2^i)^2)\) for the addition/subtraction overhead. The level-\(i\) total is \[ 7^i \cdot \Theta((n/2^i)^2) = \Theta(n^2 \cdot (7/4)^i), \] a geometric series with ratio \(> 1\).
Summing \(i = 0, \dots, \log_2 n - 1\): \[ \sum_i n^2 \cdot (7/4)^i = \Theta\left( n^2 \cdot (7/4)^{\log_2 n} \right) = \Theta(n^2 \cdot n^{\log_2(7/4)}) = \Theta(n^{2 + \log_2 7 - 2}) = \Theta(n^{\log_2 7}). \]
The leaves contribute \(7^{\log_2 n} = n^{\log_2 7}\) scalar multiplications, matching. Both contributions come together at \(\Theta(n^{\log_2 7})\).
Where the savings come from
The naive block-recursive algorithm uses 8 subproblems and gives the recurrence \(T(n) = 8 T(n/2) + \Theta(n^2)\), with critical exponent \(\log_2 8 = 3\) and complexity \(\Theta(n^3)\) — no improvement over schoolbook. Strassen’s identities trade one multiplication for \(14\) extra additions and subtractions (\(M_1\) alone uses two precomputed sums), reducing the multiplication count from 8 to 7. Because the asymptotic growth of \(T\) depends only on the number of recursive multiplications (the additions are absorbed into the \(\Theta(n^2)\) overhead), the change from \(a = 8\) to \(a = 7\) shifts the exponent from \(\log_2 8 = 3\) to \(\log_2 7 \approx 2.807\).
This is the prototype of a bilinear algorithm improvement: reducing the rank of the underlying tensor for \(2 \times 2\) matrix multiplication from \(8\) to \(7\). Subsequent improvements (Pan, Strassen, Coppersmith-Winograd, Le Gall) work on larger blocks or recursive constructions, achieving the current best \(\omega < 2.371\).
Practical caveats
The hidden constant in Strassen is large — around 7 additions per recursive level overhead — so the crossover point with the optimized schoolbook algorithm is around \(n \approx 100\). For matrices smaller than this, schoolbook (often via tuned BLAS routines) is faster. Strassen also has worse numerical stability: its backward error grows as \(O(n^{\log_2 18})\) rather than the schoolbook \(O(n^2)\), which matters for scientific computing.
Lower bound
The lower bound \(T(n) = \Omega(n^2)\) is trivial (need to read \(2 n^2\) inputs and write \(n^2\) outputs). Closing the gap between \(\Omega(n^2)\) and the current best upper bound is the central open problem in algebraic complexity. Strassen’s algorithm proved that the obvious \(\Theta(n^3)\) is not optimal — every subsequent improvement has built on the same template of finding a low-rank bilinear identity for fixed-size matrix products.