Problem Solving

Big O Notation

Students compare how quickly two rows of block stacks grow.

Big O Notation definition

Big O notation describes an eventual upper bound on how fast a function grows, ignoring a fixed multiplicative constant.

In Spanish
notación O grande
Topic
Algorithms and problem-solving

Big O Notation in a picture

Big O Notation diagramFor n ≥ 1, the expression 3n + 2 is at most 5n, so it is O(n).f(n) = 3n + 2Use n as the comparison functionFor n ≥ 1, 2 ≤ 2nSo 3n + 2 ≤ 5nC = 5 and N = 1 workThe growth is O(n)
For n ≥ 1, the expression 3n + 2 is at most 5n, so it is O(n).

How it works

For nonnegative functions, f(n) is O(g(n)) if some constants C > 0 and N make f(n) ≤ Cg(n) for every n ≥ N. An algorithm’s running time can be described this way in terms of input size. A bound can be correct even when it is looser than the best available one.

Worked examples

Is 4n² + n O(n²)?

Yes. For n ≥ 1 it is at most 5n².

Is n O(n²)?

Yes, since n ≤ n² for n ≥ 1. O(n) is the tighter upper bound.

Is n² O(n)?

No. The ratio n²/n = n grows without bound.

Common mistake

Big O gives an upper bound on growth. It does not state an exact operation count or imply the bound is tight.

Quick check

Does big O provide an upper bound or a lower bound?

Can a correct big O bound be loose?

Show answer

Yes.

Does O(n) mean exactly n operations?

Show answer

No. It compares growth for sufficiently large inputs.

Sources

Flashcard

Big O Notation

Reveal the definition

Big O notation describes an eventual upper bound on how fast a function grows, ignoring a fixed multiplicative constant.

Effortless Math. “Big O Notation.” Math Dictionary.