jsschools

Big-Omega Notation (Ω)

An asymptotic lower bound describing the best-case or minimum growth rate of an algorithm's resource usage.

Spec ↗

Syntax

f(n) = Ω(g(n))
// iff ∃ constants c > 0, n₀ > 0 such that
// f(n) ≥ c·g(n) for all n ≥ n₀

Parameters

NameTypeRequiredDescription
f(n) function Yes The actual runtime or space usage of the algorithm.
g(n) function Yes The lower-bounding function.

Returns

boolean — True if f grows at least as fast as g asymptotically.

Examples

// Any comparison-based sort is Ω(n log n) — proven by
// the decision-tree lower bound argument.
// Merge sort achieves this lower bound in all cases.

// Linear search is Ω(1) in the best case (target at index 0)
// but O(n) in the worst case.
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // might exit at i=0
  }
  return -1;
}
console.log(linearSearch([42, 1, 2, 3], 42)); // best case: Ω(1)
console.log(linearSearch([1, 2, 3, 42], 42)); // worst case: O(n)
Output 
0
3

// Lower bound example: any algorithm that reads all n inputs
// is at minimum Ω(n). Reading an array element is Ω(1).
const arr = Array.from({ length: 5 }, (_, i) => i * 10);

// Ω(1) — constant lower bound
console.log('First element:', arr[0]);

// Ω(n) — must touch every element
const total = arr.reduce((sum, x) => sum + x, 0);
console.log('Sum:', total);
Output 
First element: 0
Sum: 100

Notes

Big-Omega (Ω) is the *lower* bound — it says "the algorithm takes at least this long in the best case". Like Big-O, it drops constant factors: Ω(3n) = Ω(n). Key relationships: - f(n) = O(g(n)) means g is an upper bound on f. - f(n) = Ω(g(n)) means g is a lower bound on f. - f(n) = Θ(g(n)) means g is both (tight bound). The Ω lower bound is often used to prove that an algorithm cannot be improved beyond a certain point (e.g., any comparison sort requires Ω(n log n) comparisons in the worst case).

See also