Amdahl's law and Gustafson's law

Suppose a job takes 10 hours, and you discover that 9 of those hours could be split across many workers but 1 hour simply cannot be parallelized (it must be done by one worker, start to finish). Even with infinitely many workers, the job can never drop below that 1 hour — the serial part is a floor. That floor is the heart of Amdahl's law, and the reason throwing more cores at a problem so often disappoints.

Amdahl's law, stated plainly: if a fraction p of the work can be parallelized and the remaining serial fraction is s = 1 - p, then with N processors the best possible speedup is 1 / (s + p/N). As N grows the p/N term shrinks toward zero, so the speedup approaches 1/s, a hard ceiling set entirely by the serial fraction — if 5% is serial (s = 0.05), you can never go faster than 20x no matter how many cores you buy. The catch in Amdahl is that it holds the PROBLEM SIZE FIXED and asks how fast you can finish the same work. Gustafson's law reframes the question for the common real case where more compute lets you tackle a BIGGER problem in the same time: if you scale the work up with the machine, the serial part stays roughly constant while the parallel part grows, so the achievable scaled speedup is s + p x N, which grows nearly linearly with N. Both are correct; they answer different questions. Amdahl: 'fixed work, how much sooner can I finish?' — pessimistic, ceiling-bound. Gustafson: 'fixed time, how much more work can I do?' — optimistic, scaling-friendly.

It matters because it tells you, before you spend money on cores, what parallelism can and cannot buy. The honest cautions: real speedup is usually WORSE than even Amdahl predicts, because parallelism adds its own overheads — synchronization, communication, contention, load imbalance — that the formula ignores. And the 'serial fraction' is not fixed by nature: often the biggest win is not adding cores but shrinking s by removing a serial bottleneck (a global lock, a sequential I/O phase). Measure your actual serial fraction before assuming N cores give Nx.