How we measure cost

Big-O: how work grows with input size n — the measuring stick for the whole book.

Count operations, not seconds

Constant $O(1)$ — fixed work, any n
Linear $O(n)$ — one pass
Logarithmic $O(\log n)$ — halve the input each step
Keep the dominant term, drop the constants

The ladder

O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)

The shape is the algorithm's cost. The constant is what your hardware buys.

The shapes, growing

Linear vs binary search

Same target, same array: 20 probes vs 5. That gap is $O(n)$ vs $O(\log n)$ .

The library changes the constant, not the class

Sort at n=16000: 15.6 ms scratch vs 1.28 ms built-in (~12×)
Same-shaped curve, gentler slope
Win the Big-O first — no tuning rescues the wrong shape

Takeaway

Ask two questions of every algorithm:

What's the Big-O? (this chapter)
What's the constant? (the rest of the book)

1 / 7