ガウスの消去法の計算量 ⅓n³

最初のステップでおよそ $n^2$ 回、次のステップで $(n-1)^2$ 回と演算を数え、和 $n^2 + (n-1)^2 + \cdots + 1^2$ をとって、それを $\int_0^n x^2\,dx = \frac{1}{3}n^3$ で見積もりましょう。

右辺を一つ、同じ消去のステップに通すにはおよそ $n^2$ 回の演算がかかり、行列のコストより $n$ の次数が一つ低いことを書き留めましょう。

$\frac{1}{3}n^3$ を $L$ と $U$ のために一度だけ払い、そのあとの右辺はどれも $n^2$ しかかからないという実際的なやり方を述べましょう。