Why efficiency matters

Overview

Introduces the idea that the same problem can be solved in ways that scale very differently as input grows.

When a program is small, almost any approach works. The differences appear as the input grows: a routine that doubles its work each time the input doubles will eventually overtake a routine that adds a fixed amount of work.

We describe this growth with asymptotic notation, which deliberately ignores constant factors and small inputs so that we can compare the shape of the growth rather than machine-specific timing.