正方行列 \(A = (a_1, \ldots , a_n)^T, B = (b_1, \ldots , b_n)\) の積 \(C = AB\) を求める。

\(C_{i,j} = \sum_{k=1}^n a_i[k] b_j[k]\) に従って計算すると \(n^3\) 回の掛け算が必要である。加算回数 \(n(n-1)\) との trade off で乗算回数を減らしたい。

次のように変形する。
$$\begin{align} & \sum_{k=1}^n a_i[k] b_j[k] \\ = & \sum_{k=1}^{n/2} (a_i[2k-1] + b_j[2k])(a_i[2k] + b_j[2k-1]) \\
&-\sum_{k=1}^{n/2} a_i[2k-1]a_i[2k]-\sum_{k=1}^{n/2} b_j[2k-1]b_j[2k]
\end{align}$$

\(\sum a_i[2k-1]a_i[2k],\sum b_j[2k-1]b_j[2k]\) はそれぞれ \(a_i, b_j\) だけの式なので、全ての \(i,j\) について、\(n^2\) 回の乗算で前計算できる。一つ目の \(a_i, b_j\) が入り混じった項は \(n^3/2\) 回の乗算で計算できる。

纏めると、
乗算回数 \(n^3\) → \(n^3/2+n^2\)
加算回数 \(n(n-1)\) → \(\frac{3}{2}n^2+o(n^2)\)
となった。