Gustafson's law is a formula that predicts the speedup of a parallel program when the problem size is allowed to grow with the number of processors. It was proposed by John Gustafson in 1988 as a rebuttal to the pessimism of Amdahl's law. The key shift is moving from strong scaling (fixed problem, more cores) to weak scaling (more cores, proportionally more work).

The argument goes like this. Fix the time $T$ you are willing to spend running on $n$ processors. During that time, a sequential fraction $\alpha$ of the work is inherently serial and a fraction $1 - \alpha$ runs in parallel across all $n$ cores. Now ask: how long would the same amount of work take on a single core? The parallel portion, which $n$ cores finished in time $(1-\alpha)T$, would take a single core $n(1-\alpha)T$. The sequential portion still takes $\alpha T$. So the single-core time is:

$$T_1 = \alpha T + n(1 - \alpha)T = T\bigl(\alpha + n(1 - \alpha)\bigr)$$

The speedup is then:

$$S(n) = \frac{T_1}{T} = \alpha + n(1 - \alpha) = n - \alpha(n - 1)$$

Under Amdahl's law, speedup is bounded by $\frac{1}{1-p}$ no matter how large $n$ gets. Under Gustafson's law, speedup grows linearly with $n$ — the sequential fraction $\alpha$ only subtracts a small constant $\alpha(n-1)$ from the ideal $n\times$ speedup.

The crucial difference is the definition of $\alpha$. In Amdahl's law, $p$ is the parallelizable fraction of the single-core runtime — a fixed quantity. In Gustafson's law, $\alpha$ is the sequential fraction of the parallel runtime — and as problem size grows, computationally heavy work tends to make $\alpha$ smaller, not larger.

Amdahl's law applies when the problem is fixed in size, for example, compiling the same codebase faster or rendering the same single frame faster. Gustafson's law applies when you scale the problem alongside the hardware, for example, running a larger fluid simulation on a larger cluster, or increasing the resolution of a quantum system simulation as you add more GPUs. Most HPC workloads fall into the Gustafson regime: the reason you buy more nodes is to solve a bigger problem, not to solve the same problem faster.