Foundation · Module 1 · Lesson 1
Big O, Ω, and Θ
Upper, lower, and tight asymptotic bounds.
Lesson 1 of 123
1d streakDetailed theory
Asymptotic notation describes how resource usage grows as the input size n becomes large. It compares growth rates, not stopwatch time, and lets us reason independently of a particular computer.
By the end, you can
- Distinguish an upper bound, lower bound, and tight bound.
- Simplify operation counts into a growth class.
- Derive complexity from loops, branches, and shrinking input.
Vocabulary
Definitions with concrete meaning
O(g(n)) — upper bound
f(n) is eventually no larger than a constant multiple of g(n). It answers “how fast can the cost grow at most?”
Ω(g(n)) — lower bound
f(n) is eventually at least a constant multiple of g(n). It describes a guaranteed floor on growth.
Θ(g(n)) — tight bound
f(n) has both an O(g(n)) upper bound and an Ω(g(n)) lower bound. Its growth is pinned from both sides.
n — input size
The quantity that controls work: array length, number of nodes, digits, vertices V, edges E, or another explicit measure.
Rules to apply
- 1Drop constant factors: Θ(7n) becomes Θ(n).
- 2Keep the fastest-growing term: Θ(n² + n + 1) becomes Θ(n²).
- 3Sequential blocks add, then simplify: Θ(n) + Θ(n²) = Θ(n²).
- 4Nested independent loops multiply: n iterations × n iterations = Θ(n²).
- 5For if/else branches, use the cost of the branch being analyzed—usually the maximum for worst case.
- 6Repeatedly halving or doubling until n is reached produces Θ(log n) iterations.
Worked example 1
Simplify an exact operation count
An algorithm performs f(n) = 4n² + 3n + 12 primitive operations.
- 1
Find the dominant term
n² grows faster than n and a constant, so 4n² controls large inputs.
- 2
Drop its constant factor
Asymptotic classes ignore machine-dependent constant multipliers: 4n² → n².
- 3
State a useful bound
The function is O(n²), Ω(n²), and therefore Θ(n²).
Use Θ(n²) when you know the tight growth rate; O(n²) alone is correct but weaker.
Worked example 2
Count a triangular nested loop
The inner loop starts at i + 1 instead of running n times for every i.
for i = 0 to n - 1:
for j = i + 1 to n - 1:
compare(a[i], a[j])- 1
Count each row
The inner loop runs n−1, n−2, …, 1, 0 times.
- 2
Sum the work
(n−1) + (n−2) + … + 1 = n(n−1)/2.
- 3
Simplify
(n²−n)/2 has dominant term n², so the work is Θ(n²).
A shrinking inner loop can still be quadratic; count the total iterations.
Comparison table
Common growth rates
These values show why the growth class matters more as n increases. Values are approximate where noted.
| Class | Typical pattern | n = 10 | n = 100 |
|---|---|---|---|
| Θ(1) | Direct lookup | 1 | 1 |
| Θ(log₂ n) | Halve the search space | ≈ 3.3 | ≈ 6.6 |
| Θ(n) | One full scan | 10 | 100 |
| Θ(n log₂ n) | Efficient comparison sort | ≈ 33 | ≈ 664 |
| Θ(n²) | All pairs | 100 | 10,000 |
| Θ(2ⁿ) | Include/exclude choices | 1,024 | ≈ 1.27 × 10³⁰ |
Check your understanding
1Is saying “binary search is O(n)” false?
No, but it is loose. Θ(log n) is the informative tight bound, and O(log n) is the useful upper bound.
2Why is O(2n + 100) simplified to O(n)?
For sufficiently large n, the linear term controls growth; constants do not change the growth class.
3Do two consecutive O(n) loops make O(n²)?
No. Their costs add: O(n + n) = O(2n) = O(n). Only nested work multiplies.
Cost Model
Complexity & Trade-offs
When to use it
- Comparing algorithms independently of hardware and programming language.
- Checking whether an approach fits an input constraint.
- Explaining performance trade-offs in interviews and design reviews.
Common mistakes
- Treating Big O as an exact runtime or automatically as the worst case.
- Using O when claiming equality; Θ communicates a known tight growth rate.
- Multiplying consecutive loops or ignoring work hidden inside a loop body.
Practice prompts
- Derive the tight bound for a triangular nested loop.
- Order 1, log n, n, n log n, n², 2ⁿ, and n! by growth.
- Find separate bounds in terms of rows and columns for a matrix scan.
Mastery check