Counting the Work

Two programs can produce identical answers and be wildly different in value. The question complexity answers is: as the data grows, how fast does the work grow?

We do not measure in seconds, because seconds depend on the machine. We count operations relative to the size of the input, and we call that size n.

Constant time. The work does not depend on n at all. Reading items[0] takes the same time whether the list holds ten items or ten million.

Linear time. One pass through the data. Ten times the data means ten times the work. Every loop you have written so far is linear.

Quadratic time. A loop inside a loop. Ten times the data means one hundred times the work. This is where programs stop being usable.

✦ The number that should alarm you

With 1000 items, a linear loop does 1000 operations. A nested loop does 1,000,000. With 100,000 items, linear does 100,000 and nested does ten billion. Same correct answer, one finishes instantly and the other never finishes at all.