Little-omega Notation

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

f(n) = ω(g(n)) means f(n) grows strictly faster than g(n).

◇Details / Theory

◇Strict Lower Bound.

f(n) = ω(g(n)) means f(n) grows strictly faster than g(n). lim (n→∞) f(n)/g(n) = ∞.
Example: n³ = ω(n²). n² is not ω(n²).

◇Complexity

◇Common Pitfalls

Confusing little-omega with Big-Omega — little-omega is strictly greater, while Big-Omega allows equality. Mixing up the limit definition: $f(n)/g(n) \to \infty$, not $0$.

◇Summary

TL;DR — Little-omega ($\omega$) gives a strict lower bound: $f(n) = \omega(g(n))$ means $f$ grows strictly faster than $g$. It is the transpose of little-o.

◇Links

Related: Source / Reference:

◇References & Navigation

• Previous Topic: ◇Little-o Notation
• Next Topic: ◇Loops
• Related Notes: ◇Asymptotic Notation, ◇Big-O Notation