0 · Recall Warm-up
Answer from memory first. Answers are in the Answer Vault at the bottom.
- Is 2²ⁿ = O(2ⁿ)? from Lesson 1.1.1
- log₃ n vs log₂ n? from Lesson 1.1.1
- a^(log n) = ? from Lesson 0.1.2
1 · The Hook
🎣
GATE's favourite asymptotic question: "arrange these functions in increasing order of growth". The functions look strange (n^(log n), 2ⁿ, n^(3/2), (log n)!) but two tools settle every case: the limit of the ratio, and taking logs of both sides.
2 · Predict First
🤔
Which grows faster: n^(log n) or 2ⁿ? (Hint: compare their logarithms.)
Make a guess in your head. The answer opens Section 3.
3 · Core Concept
💡
Predict First — the answer
log(n^(log n)) = (log n)² and log(2ⁿ) = n. Since n grows much faster than (log n)², 2ⁿ grows faster.
Little-o and little-ω (strict)
- f = o(g) if f(n)/g(n) → 0: f grows strictly slower. (n = o(n²); n² ≠ o(n²).)
- f = ω(g) if f(n)/g(n) → ∞: f grows strictly faster.
The limit test
Compute L = lim f(n)/g(n):
| L | Conclusion |
|---|---|
| 0 | f = o(g) (so also O(g), not Ω) |
| constant > 0 | f = Θ(g) |
| ∞ | f = ω(g) (so also Ω(g), not O) |
The log trick
To compare f and g, compare log f and log g. If log f − log g → ∞, then f grows faster. (Careful: log f = Θ(log g) does not imply f = Θ(g): log(n²) = Θ(log n) but n² ≠ Θ(n).)
The standard growth ladder
1 < log log n < log n < (log n)ᵏ < n^ε < n < n log n < n^(1+ε) < n² < n³ < n^(log n) < 2ⁿ < 3ⁿ < n! < nⁿ (k any constant, 0 < ε < 1.) Polylogs lose to every positive power of n; every polynomial loses to every exponential.
Useful identities
- n^(1/log n) = 2: a constant.
- log(n!) = Θ(n log n); n! = o(nⁿ); n! = ω(2ⁿ).
- 2^(log n) = n; 2^(√(log n)) grows slower than any n^ε.
- √n = n^(1/2) beats (log n)¹⁰⁰ eventually.
Properties
- Transitive: f = O(g), g = O(h) ⇒ f = O(h) (also Ω, Θ, o, ω).
- Reflexive: f = O(f), Ω(f), Θ(f) (not o(f)).
- Symmetric: f = Θ(g) ⇔ g = Θ(f). Transpose: f = O(g) ⇔ g = Ω(f).
4 · Visual
| Pair | Compare logs | Winner |
|---|---|---|
| n^(log n) vs 2ⁿ | (log n)² vs n | 2ⁿ |
| n^(√n) vs 2ⁿ | √n log n vs n | 2ⁿ |
| n^(3/2) vs n log n | ratio n^(1/2)/log n → ∞ | n^(3/2) |
| 2ⁿ vs n! | n vs log n! ≈ n log n | n! |
| (log n)^(log n) vs n² | (log n)(log log n) vs 2 log n | (log n)^(log n) |
5 · Worked Examples
Example 1 Easy
Order: n log n, n², √n, log n.
Solution
log n < √n < n log n < n².
Example 2 Medium
Order f₁ = 2ⁿ, f₂ = n^(3/2), f₃ = n log n, f₄ = n^(log n).
Solution
f₃ < f₂ < f₄ < f₁: n log n < n^1.5 (ratio √n/log n → ∞); n^1.5 < n^(log n) (exponent log n > 1.5 eventually); n^(log n) < 2ⁿ (logs (log n)² vs n).
Example 3 GATE
Is n^(1/log n) = Θ(1)?
Solution
Yes: n^(1/log n) = 2^(log n · 1/log n) = 2.
6 · GATE Traps
⚠️
- o and ω are strict: f ≠ o(f).
- Equal growth of logs does not mean equal growth.
- (log n)ᵏ is smaller than n^0.001 for large n, whatever k.
- n^(log n) is super-polynomial but sub-exponential.
7 · Memory Hook
🧠
"Ratio to zero: slower. Ratio to a constant: same. Ratio to infinity: faster. When stuck, take logs."
8 · Connect the Dots
You can now compare any two functions. Next: produce the functions in the first place, by counting the iterations of loops, nested and dependent, doubling and halving.
9 · Self-Test
GATE format. Try every question before opening the vault.
Q1MCQ2 marksOrdering
Arrange in increasing order of growth: f₁ = n^(√n), f₂ = 2^(√n), f₃ = n², f₄ = n log² n.
- (A) f₄, f₂, f₃, f₁
- (B) f₄, f₃, f₂, f₁
- (C) f₃, f₄, f₂, f₁
- (D) f₄, f₃, f₁, f₂
Q2MCQ1 markLimit test
If lim f(n)/g(n) = 5, then:
- (A) nothing can be said
- (B) f = o(g)
- (C) f = Θ(g)
- (D) f = ω(g)
Q3MSQ2 marksFacts
Which are true?
- (A) (log n)⁵⁰ = o(n^0.1)
- (B) n = o(n)
- (C) n! = O(2ⁿ)
- (D) log(n!) = Θ(n log n)
Q4MCQ1 markLog trick
Which grows fastest?
- (A) n¹⁰
- (B) n^(log log n)
- (C) 2^(√n)
- (D) (log n)^(log n)
Q5MCQ1 markTranspose
If f = O(g), then necessarily:
- (A) f = Θ(g)
- (B) g = O(f)
- (C) g = Ω(f)
- (D) f = o(g)
10 · Rule Card
- o: f/g → 0; ω: f/g → ∞; constant limit → Θ.
- Compare logs when stuck (but equal logs ≠ equal growth).
- Ladder: 1 < log log n < log n < polylog < n^ε < n < n log n < n² < … < n^(log n) < 2ⁿ < 3ⁿ < n! < nⁿ.
- n^(1/log n) = 2; log n! = Θ(n log n); transitivity, reflexivity, symmetry (Θ), transpose (O/Ω).
11 · Concept Ledger
Unlocked in this lesson. From here on, these terms may be used.
little-olittle-ωlimit testcomparing logarithmsgrowth ladderpolylogarithmicsuper-polynomialtransitivity, reflexivity, symmetry, transpose symmetry
12 · Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Recall Warm-up
- No: 2²ⁿ/2ⁿ = 2ⁿ is unbounded.
- Θ of each other (bases differ by a constant factor).
- n^(log a).
Self-Test
Q1 Answer: (B)2 marks
Logs: f₄ ≈ log n, f₃ = 2 log n, f₂ = √n, f₁ = √n log n.
- (A) is wrong: 2^(√n) beats n² (√n vs 2 log n).
- (C) is wrong: n log² n < n².
- (D) is wrong: 2^(√n) < n^(√n).
Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functions
Q2 Answer: (C)1 mark
A positive finite limit means the same growth.
- (A) is wrong: The limit decides it.
- (B) is wrong: Needs limit 0.
- (D) is wrong: Needs limit ∞.
Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functions
Q3 Answer: (A) (D)2 marks
n! grows faster than 2ⁿ; nothing is o of itself.
- (B) is wrong: o is strict.
- (C) is wrong: n!/2ⁿ → ∞.
Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functions
Q4 Answer: (C)1 mark
Logs: (log log n)(log n), (log log n)(log n), √n, 10 log n; √n wins.
- (A) is wrong: Polynomial.
- (B) is wrong: Log is (log n)(log log n), smaller than √n.
- (D) is wrong: Same log as A: n^(log log n) = (log n)^(log n).
Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functions
Q5 Answer: (C)1 mark
Transpose symmetry.
- (A) is wrong: Not necessarily.
- (B) is wrong: Not necessarily (n = O(n²)).
- (D) is wrong: Not necessarily (f = O(f) but not o(f)).
Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functions