Big O Notation definition
Big O notation describes an eventual upper bound on how fast a function grows, ignoring a fixed multiplicative constant.
Big O Notation in a picture
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
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.
