Formal Definition of Big-Omega
What you'll learn: You'll understand the precise mathematical definition of Big-Omega notation and what it means for a function to be bounded below.
The Core Idea
Big-Omega (Ω) describes the lower bound of a function's growth rate. While Big-O gives an upper limit ("at most this fast"), Big-Omega gives a lower limit ("at least this fast"). It tells us the minimum amount of work an algorithm must do in the best possible scenario—or more generally, that a function grows at least as fast as another function.
The Mathematical Definition
We say f(n) = Ω(g(n)) if and only if:
There exist positive constants c and n₀ such that f(n) ≥ c·g(n) for all n ≥ n₀
Let's unpack this:
- f(n) is the function we're analyzing (like your algorithm's runtime)
- g(n) is the simpler function we're comparing it to (like n, n², etc.)
- c is a positive constant multiplier
- n₀ is the point beyond which the relationship holds
- The inequality f(n) ≥ c·g(n) means f grows at least as fast as some constant multiple of g
Concrete Example
Suppose f(n) = 3n² + 5n. To prove f(n) = Ω(n²), we need to show that for large enough n, f(n) stays above some constant times n².
If we choose c = 3 and n₀ = 0, then for all n ≥ 0:
3n² + 5n ≥ 3n² ✓
Since 3n² + 5n is always at least 3n², we've proven f(n) = Ω(n²).
Key Takeaway: Big-Omega provides a lower bound on growth—f(n) = Ω(g(n)) guarantees that f grows at least as fast as some constant multiple of g for all sufficiently large inputs.