Big O Notation

What is this?

Writing O(n²) says: beyond some input size, this algorithm's cost is at most a constant multiple of n². It is an upper bound on the growth rate, nothing more.

What it deliberately discards

Two things are thrown away, and knowing which two makes the notation easy to apply.

Constant factors. 3n and 100n are both O(n). The 100 matters in practice but it is a property of your implementation, not of the algorithm.
Lower-order terms. n² + n + 500 is O(n²), because once n is large the n² term dwarfs the rest.

Simplifying an operation count

InputT(n) = 4n² + 30n + 900

4n² + 30n + 900the raw operation count
n² + n + 1drop the constant multipliers
n²keep only the fastest-growing term

ResultO(n²)

The family of growth rates

Notation	Name	n = 1,000 costs roughly
O(1)	Constant	1
O(log n)	Logarithmic	10
O(n)	Linear	1,000
O(n log n)	Linearithmic	10,000
O(n²)	Quadratic	1,000,000
O(2ⁿ)	Exponential	more than atoms in the observable universe

Relative cost at a thousand items.

Best, average and worst

The same algorithm can have three different answers depending on which input you consider.

python

1def find(nums, target):2    for i, value in enumerate(nums):3        if value == target:4            return i5    return -1

Linear search

Best case: the target is first. One comparison, O(1).
Worst case: the target is absent. n comparisons, O(n).
Average case: with the target equally likely anywhere, about n/2 comparisons — still O(n).

When someone says this is O(n) without qualification, they mean the worst case. That is the convention, because the worst case is the only one you can promise.

Common mistakes

Saying an algorithm is O(n²) when you mean it is exactly n² — Big O is an upper bound, so O(n²) is technically true of a linear algorithm too, just useless.
Dropping a term that is not actually lower-order: n · m does not simplify to n when m is a separate input.
Reporting the best case because it sounds better.
Ignoring the cost of a built-in: a slice, a sort or a string concatenation inside a loop all carry their own complexity.

Quick quiz

Reading Big O

1Simplify T(n) = 4n² + 30n + 900 to Big O notation.

O(4n²)

O(n² + n)

O(n²)

O(n² + 900)

2An algorithm is described simply as O(n). Which case does that describe by convention?

Best case

Average case

Worst case

Whichever the author measured

3What is the time complexity of this function?

def build(chars):
    out = ""
    for char in chars:
        out += char
    return out

O(n)

O(n²)

O(n log n)

O(1)