What Big-O measures

Big idea

Big-O describes how the number of steps grows with the input size n, ignoring constant factors and smaller terms. It answers "what happens when n gets 10× bigger?", not "how many milliseconds does this take?".

Count steps, not seconds

Seconds depend on your laptop, the language, and what else is running. Steps don't. So instead of timing code, count how many basic operations — a comparison, an addition, an array read — it does for an input of size n.

def total(nums):
    s = 0              # 1 step
    for x in nums:     # runs n times
        s += x         # 1 step each time
    return s           # 1 step

That's about n + 2 steps. For n = 1,000 it's 1,002; for n = 1,000,000 it's 1,000,002. The + 2 stops mattering almost at once — what matters is that the work grows in step with n. We write that as O(n), "linear time".

Drop constants and smaller terms

Suppose a function does 3n² + 5n + 20 steps. At n = 1,000:

The n² term swamps everything else, and the 3 in front doesn't change how it grows — double n and the cost still roughly quadruples. So 3n² + 5n + 20 is O(n²).

Two rules cover most cases:

• Keep the fastest-growing term. n² + n → O(n²). n + log n → O(n).
• Drop constant multipliers. 3n → O(n). n/2 → O(n). 500 → O(1).

Watch it

Worst, best, and average case

The same algorithm can take different paths on different inputs. Searching a list for a value:

def find(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1

• Best case: the target is first — 1 step.
• Worst case: it's last or missing — n steps.
• Average case: about n/2 steps if the target is equally likely to be anywhere.

When people say "this is O(n)" without qualifying, they almost always mean the worst case. It's the honest promise: no input of size n will be slower than this.

O, Ω, and Θ in one line each

• O(f) — an upper bound: grows no faster than f.
• Ω(f) — a lower bound: grows at least as fast as f.
• Θ(f) — both: grows exactly like f.

In interviews, "O" is used loosely to mean the tight bound. Saying linear search is O(n²) is technically true (n² is an upper bound) but useless — always give the tightest bound you can.

Quick check