Big O notation
The O, Ω and Θ notations, their definition by a constant and a threshold, the rules for simplifying a cost and the scale of growth classes, from 1 to n!.
- 26 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- The curves
A few cards from the deck
Asymptotic upper bound: what is it?
Show the answer
Saying f is in O(g) means there is a constant c > 0 and a threshold n₀ such that f(n) ≤ c × g(n) for every n ≥ n₀.
The constant absorbs machine details and the threshold sets small sizes aside: only the growth matters. 3n + 10 is in O(n) with c = 4 and n₀ = 10.
An algorithm costs T(n) = 3n² + 40 n log n operations. Which Θ class is it in?
- Θ(n²)
- Θ(n log n)
- Θ(n² log n)
- Θ(n³)
Show the answer
Θ(n²)
n² grows faster than n log n: the n² term dominates and the coefficient 3 disappears. The two terms add: they are not multiplied to get n² log n.
If f is in both O(g) and Ω(g), then f is in …(g).
Show the answer
If f is in both O(g) and Ω(g), then f is in Θ(g).
Θ bounds the cost from both sides: it is the only notation that says "exactly this growth".