1.1Growth rates and Big-O, Ω, Θ
The idea
Asymptotic notation describes how running time grows when the input gets large, ignoring constants. Big-O is an upper bound, Ω a lower bound, Θ both.
Think of it like this: Comparing cars by top speed, not by how fast they leave the driveway: only the long-run behaviour matters.
Why it exists
It lets you compare algorithms without a stopwatch, and every GATE algorithm question ends in one of these classes.
How it works
- Write the exact count as a formula in n.
- Drop constant factors and lower-order terms: 3n² + 5n + 7 → n².
- Compare growth using the ladder: log n < √n < n < n log n < n² < n³ < 2ⁿ < n!.
- Remember the exponent traps: 2²ⁿ = 4ⁿ is bigger than 2ⁿ by more than a constant.
Worked example: Is 2ⁿ⁺¹ = O(2ⁿ)?
2ⁿ⁺¹ = 2 · 2ⁿ, a constant multiple, so yes (even Θ). But 2²ⁿ = (2ⁿ)² is not O(2ⁿ).
Now play with it
- →Type n = 50 and compare 2ⁿ, n³ and n log n.
- →Find the n where 2ⁿ passes n² (around n = 5).
Try n = 10, 20, 50, 100: 2ⁿ overtakes every polynomial almost immediately, while log n barely moves.
| f(n) | g(n) | relationship | why |
|---|---|---|---|
| n² + 5n | n² | f = Θ(g) | drop lower-order terms and constants |
| 2ⁿ⁺¹ | 2ⁿ | f = Θ(g) | 2ⁿ⁺¹ = 2 · 2ⁿ, a constant factor |
| 2²ⁿ | 2ⁿ | f = ω(g), not O(g) | 2²ⁿ = 4ⁿ = (2ⁿ)², the constant is in the exponent |
| log n! | n log n | f = Θ(g) | Stirling |
| n^(log n) | 2ⁿ | f = o(g) | n^(log n) = 2^((log n)²) and (log n)² ≪ n |
| (log n)^(log n) | n² | f = ω(g) | (log n)^(log n) = n^(log log n), and log log n grows |
| √n | log² n | f = ω(g) | every positive power of n beats every power of log n |
| n! | 2ⁿ | f = ω(g) | n! ≈ (n/e)ⁿ |
The "log n versus power of n" and "constant in the exponent" rows are the usual exam traps.
Check yourself
Which is true?
Exam notes (the dense version)
f = O(g) means f grows no faster than g, Ω(g) no slower, Θ(g) both. Order to remember: 1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ. Constants and lower-order terms vanish. Polynomials beat any power of log; exponentials beat any polynomial. log(n!) = Θ(n log n).
Previous year questions: Asymptotic Analysis & Recurrences (16)
PYQs are grouped by topic, so this is the full set for Asymptotic Analysis & Recurrences; try the ones that match this subtopic. Open all 16 on the topic page.