n = 100
≈ 2n³/3 = 666 667 flops
Leading term.
Gaussian elimination on a dense system takes about arithmetic operations (plus for back-substitution). Doubling multiplies the work by 8.
This page is easier if you are comfortable with:
For : operations; for : , a thousand times more for ten times the size. A computer doing operations per second solves the system in under a second, but would need operations, about a week. Each of the elimination steps updates a shrinking square block, giving multiplications and as many additions (the sum of squares, compare sums of squares).
For banded or sparse matrices the cost is far lower (tridiagonal systems cost , used in Crank–Nicolson schemes), and iterative methods (Jacobi and Gauss–Seidel) cost per sweep for dense matrices. The comparison with the fast Fourier transform's (FFT cost) shows why structure matters.
Accuracy, not just cost, depends on the problem (the condition number) and on pivoting. The elimination steps are the row operations used for determinants and inverses (solving a linear system, determinants).
Gaussian elimination costs about two thirds of n cubed operations for a dense system.
The cost rises steeply with the size of the system.
These examples are worked by hand, step by step, so you can compare your own working.
Estimate the operations for .
Estimate the operations for .
By what factor does the work grow when is doubled?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
≈ 2n³/3 = 666 667 flops
Leading term.
≈ 6.67 × 10⁸ flops
1000 times more for 10× n.
cost × 8
Cubic growth.
≈ n² flops
Much cheaper.
Gaussian elimination on an n × n system costs about 2n³/3 floating-point operations; back substitution adds about n². Doubling n multiplies the cost by 8.
Estimate the flops for n = 100.
Estimate the flops for n = 1000 in units of 10⁸.
By what factor does the cost grow when n doubles?
At 10⁹ flops/second, how long for n = 1000? (seconds)
cost ∝ n² ✗
cost ∝ n³ ✓
Elimination is cubic.
n³ flops ✗
2n³/3 ✓
Constant factor.
total = elimination only ✗
add n² ✓
Lower-order term.
one operation ✗
two flops ✓
Convention matters.
Try each one on paper, then open the answer. Use the solver above to see the full working.
18000
18
27
2500
667
18
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
About 2n³/3 flops.
About n².
Cost multiplies by 8.
For large sparse systems.
Jacobi and Gauss–Seidel.
FFT cost.
More in Numerical methods and optimisation and the formula sheets.