Course contentsShow
← Computer Science
Lesson 297 of 2,8727. Introduction to Complexity AnalysisFree lesson

Formal Definition of Big-Omega

Learning the mathematical definition: f(n) = Ω(g(n)) if there exist constants c, n₀ such that f(n) ≥ cg(n) for all n ≥ n₀.

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.