Gaussian Elimination Cost Explained with Worked Examples

Gaussian elimination on a dense system takes about arithmetic operations (plus for back-substitution). Doubling multiplies the work by 8.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Gaussian elimination cost means

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).

What is it used for?

Gaussian elimination costs about two thirds of n cubed operations for a dense system.

How to use gaussian elimination cost

  1. Identify the size of the dense system.
  2. Operations .
  3. Divide by the machine speed for the time.
  4. Use structure (banded, sparse) to reduce the cost.

Graph

Operations 2n³/3: doubling n costs eight times moren = 10: 667024681012020040060080010001200Operations 2n³/3: doubling n costs eight times morenoperations2n³/3Graph with x from 0 to 12 and y from 0 to 1200. Shows the curve 2n³/3; point n = 10: 667 at (10, 666.7).

The cost rises steeply with the size of the system.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: n = 100

Estimate the operations for .

Worked example
Answer
6.7×1056.7\times10^{5}
  1. Formula

Example 2: n = 1000

Estimate the operations for .

Worked example
Answer
6.7×1086.7\times10^{8}
  1. Formula

Example 3: doubling n

By what factor does the work grow when is doubled?

Worked example
Answer
88
  1. Formula

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

n = 100

≈ 2n³/3 = 666 667 flops

Leading term.

n = 1000

≈ 6.67 × 10⁸ flops

1000 times more for 10× n.

Doubling n

cost × 8

Cubic growth.

Back substitution

≈ n² flops

Much cheaper.

Word problems

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.

n = 100

Estimate the flops for n = 100.

  1. 2n³/32 × 10⁶/3
  2. Check: 666 667 ✓≈ 666 667.

n = 1000

Estimate the flops for n = 1000 in units of 10⁸.

  1. 2 × 10⁹/3
  2. Check: 6.67 ✓6.67.

Doubling Higher

By what factor does the cost grow when n doubles?

  1. 2³
  2. Check: ✓8.

Time estimate Higher

At 10⁹ flops/second, how long for n = 1000? (seconds)

  1. 6.67 × 10⁸ ÷ 10⁹
  2. Check: ✓0.667 s.

Common mistakes

Quadratic cost

cost ∝ n² ✗

cost ∝ n³ ✓

Elimination is cubic.

Forgetting 2/3

n³ flops ✗

2n³/3 ✓

Constant factor.

Ignoring back substitution

total = elimination only ✗

add n² ✓

Lower-order term.

Counting a multiply-add as 1

one operation ✗

two flops ✓

Convention matters.

Exam tips

  1. ≈ 2n³/3.
  2. Double n: ×8.
  3. Back substitution n².
  4. Use iterative methods for huge sparse systems.
  5. Cost ≠ accuracy.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. 2n³/3 for n = 30 Foundation

18000

2. 2n³/3 for n = 300 in millions Foundation

18

3. Factor when n triples Foundation

27

4. n² for n = 50 Higher

2500

5. 2n³/3 for n = 10 Higher

667

6. Time at 10⁹ flops/s for n = 3000 (s) Higher

18

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Gaussian elimination
Row reduction to triangular form.
Flop
Floating-point operation.
Back substitution
Solving the triangular system.
LU decomposition
Same cost as elimination.
Sparse matrix
Mostly zeros.
Complexity
Growth of cost with n.

Frequently asked questions

What is the cost of Gaussian elimination?

About 2n³/3 flops.

What about back substitution?

About n².

What happens when n doubles?

Cost multiplies by 8.

When use iterative methods?

For large sparse systems.

Which page covers Jacobi and Gauss–Seidel?

Jacobi and Gauss–Seidel.

Which page covers the FFT cost?

FFT cost.

More in Numerical methods and optimisation and the formula sheets.