- 2070 Magh · 2 marks
Small o vs small omega
Short answer
Small o: f grows strictly slower than g (lim f/g = 0, strict upper bound). Small ω: f grows strictly faster (lim f/g = ∞, strict lower bound). Example: n = o(n²) but n² ≠ o(n²); n² = ω(n) but n² ≠ ω(n²).
Differentiate between small o and small ω notations.
| Point | Small o | Small ω |
|---|---|---|
| Meaning | f grows strictly slower than g | f grows strictly faster than g |
| Definition | f(n) < c·g(n) for every c > 0, for n ≥ n₀ | f(n) > c·g(n) for every c > 0, for n ≥ n₀ |
| Limit | lim f(n)/g(n) = 0 | lim f(n)/g(n) = ∞ |
| Bound type | Strict upper bound | Strict lower bound |
| Relation to big forms | o ⊂ O (not tight) | ω ⊂ Ω (not tight) |
| Example | n = o(n²), but n² ≠ o(n²) | n² = ω(n), but n² ≠ ω(n²) |
| Analogy | f < g | f > g |
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Static vs dynamic implementation of list · Data Structure and Algorithm, chapter 3 · asked 2×
- Primitive vs non-primitive data structure · Data Structure and Algorithm, chapter 1
- Static vs dynamic list; getnode and freenode · Data Structure and Algorithm, chapter 3
- Singly vs doubly linked list · Data Structure and Algorithm, chapter 4
- Stable vs unstable sorting; heap · Data Structure and Algorithm, chapter 7
- Large vs small scale models; propagation mechanisms · Wireless Communication, chapter 3
- k-epsilon and k-omega SST models · Applied Computational Fluid Dynamics, chapter 5
- Unique vs non-unique address decoding · Instrumentation II, chapter 2
- Marconi transmitter, mobile vs nomadic, Telecom Act · Telecommunications, chapter 1