Counting without a stopwatch

Timing a program tells you about your laptop. Big O tells you about the program, and it is what lets you answer "will this survive a million items" before writing it.

It asks one question: as the input grows, how does the work grow?

Reading a loop

for x in items:          # n iterations
    print(x)             # 1 unit of work each

n items, one unit each: O(n). Double the input, double the work.

for x in items:          # n
    for y in items:      # n again, for each x
        compare(x, y)

n times n: O(n²). Double the input, quadruple the work.

The shapes, and what they feel like

Read the last row again. A million items in a quadratic algorithm is a trillion operations, which is hours. The same input in an O(n log n) algorithm is twenty million, which is under a second.

What is thrown away

Big O keeps the term that dominates and drops everything else, because everything else stops mattering as n grows:

3n² + 500n + 9000   becomes   O(n²)

At n = 1,000,000 the n² term is three trillion and the rest is half a billion. The rest is a rounding error.

Best, average, worst

Finding a name in a list: first item is O(1), last is O(n). Big O usually means the worst case, because that is the one that decides whether the program survives a bad day.