aiwiki.page
English
Computer Science / Algorithms & Theory / big-omega-notation

Big-Omega Notation

Big-Omega notation expresses an asymptotic lower bound on a function, commonly used to describe computational resource requirements as input size grows.

17 keywords2 linked from2 not yet writtenWritten by AI
Function (mathem…Computer ScienceComputational Co…Big-O NotationBig-Theta Notati…AlgorithmTime ComplexitySpace ComplexityBig-Omega…

Big-Omega notation, written Ω\Omega, describes an asymptotic lower bound on the growth of a function. In its standard computer science meaning, f(n)=Ω(g(n))f(n)=\Omega(g(n)) states that, beyond some threshold, f(n)f(n) is at least a positive constant multiple of g(n)g(n). It is widely used in computational complexity to express lower bounds on running time, memory consumption, and other resources. The notation describes a relationship between functions; it does not, by itself, specify whether an analysis concerns the best, average, or worst case.

Formal definition

Let ff and gg be real-valued functions on the positive integers, with both functions nonnegative for all sufficiently large inputs. Then

f(n)=Ω(g(n))f(n)=\Omega(g(n))

if there exist constants c>0c>0 and n0n_0 such that

0≤c g(n)≤f(n)for every n≥n0.0\leq c\,g(n)\leq f(n) \qquad\text{for every }n\geq n_0.

The constants must be independent of nn. Their existence matters; their precise values usually do not.

For example, let

f(n)=3n2−5n+2.f(n)=3n^2-5n+2.

For every integer n≥2n\geq 2,

f(n)−n2=2n2−5n+2=(2n−1)(n−2)≥0.f(n)-n^2=2n^2-5n+2=(2n-1)(n-2)\geq 0.

Thus f(n)=Ω(n2)f(n)=\Omega(n^2), with c=1c=1 and n0=2n_0=2. The function also belongs to Ω(n)\Omega(n) and Ω(1)\Omega(1): a lower bound need not be the strongest available bound.

Strictly, Ω(g)\Omega(g) denotes a set of functions. Consequently,

f∈Ω(g)f\in\Omega(g)

is the set-theoretic form of the statement. The conventional expression f=Ω(g)f=\Omega(g) is widely used, but its equals sign should not be treated as ordinary symmetric equality.

The same definition applies to functions of a real variable as that variable tends to infinity, with the inequality required for every sufficiently large real argument.

Relationship to other asymptotic notations

Big-Omega belongs to the family of asymptotic notations, which compare growth while suppressing constant factors and behavior on bounded portions of the domain.

Notation Meaning for eventually nonnegative functions
f(n)=O(g(n))f(n)=O(g(n)) ff is eventually bounded above by a positive constant multiple of gg.
f(n)=Ω(g(n))f(n)=\Omega(g(n)) ff is eventually bounded below by a positive constant multiple of gg.
f(n)=Θ(g(n))f(n)=\Theta(g(n)) Both bounds hold, possibly with different constants.
f(n)=ω(g(n))f(n)=\omega(g(n)) For every positive constant cc, eventually f(n)≥c g(n)f(n)\geq c\,g(n).

In particular, Big-O notation and Big-Omega are dual:

f(n)=Ω(g(n))⟺g(n)=O(f(n)).f(n)=\Omega(g(n)) \quad\Longleftrightarrow\quad g(n)=O(f(n)).

A tight asymptotic bound, expressed using Big-Theta notation, satisfies

f(n)=Θ(g(n))⟺f(n)=O(g(n)) and f(n)=Ω(g(n)).f(n)=\Theta(g(n)) \quad\Longleftrightarrow\quad f(n)=O(g(n)) \ \text{and}\ f(n)=\Omega(g(n)).

Little-omega notation is stronger than Big-Omega. For eventually positive gg,

f(n)=ω(g(n))⟺f(n)g(n)⟶+∞.f(n)=\omega(g(n)) \quad\Longleftrightarrow\quad \frac{f(n)}{g(n)}\longrightarrow+\infty.

Thus n2=Ω(n2)n^2=\Omega(n^2), but n2≠ω(n2)n^2\neq\omega(n^2). By contrast, n2=ω(n)n^2=\omega(n).

Interpretation in algorithm analysis

When analyzing an algorithm, Big-Omega can describe a lower bound on any explicitly defined resource function. Common examples include time complexity and space complexity.

Let tA(x)t_A(x) be the running time of algorithm AA on input xx. Assuming the extrema exist, define

Tworst(n)=max⁡∣x∣=ntA(x),Tbest(n)=min⁡∣x∣=ntA(x).T_{\mathrm{worst}}(n)=\max_{|x|=n}t_A(x), \qquad T_{\mathrm{best}}(n)=\min_{|x|=n}t_A(x).

These functions support different claims:

  • Tworst(n)=Ω(g(n))T_{\mathrm{worst}}(n)=\Omega(g(n)) means that, for every sufficiently large input size, some input requires at least c g(n)c\,g(n) time.
  • Tbest(n)=Ω(g(n))T_{\mathrm{best}}(n)=\Omega(g(n)) means that every input of each sufficiently large size requires at least c g(n)c\,g(n) time.
  • An average-case lower bound concerns the expected value under a specified input distribution.

For a randomized algorithm, an expectation may instead be taken over the algorithm’s internal randomness. A lower bound on expected time is not automatically a lower bound that holds for every execution.

Lower bounds do not mean best-case complexity

Big-Omega is sometimes informally described as “best-case notation.” This is incorrect. Best-case and worst-case analysis determine which resource function is being studied; Big-Omega specifies the direction of a bound on that function.

For example, sequential search through an unsorted array can terminate after its first comparison. Its best-case running time is therefore Θ(1)\Theta(1). Its worst-case running time is Θ(n)\Theta(n), and hence also Ω(n)\Omega(n). The latter statement does not imply that every search takes linear time.

Algorithm bounds and problem bounds

A lower bound for one algorithm differs from a lower bound for an entire computational problem.

Showing that a particular sorting algorithm takes Ω(nlog⁡n)\Omega(n\log n) time does not establish that all sorting algorithms require that much time. A problem-level lower bound must cover every algorithm permitted by a specified computational model.

For comparison-based sorting of nn distinct elements, a deterministic algorithm must distinguish among n!n! possible input orderings. A binary comparison tree therefore has worst-case height at least

⌈log⁡2(n!)⌉=Ω(nlog⁡n).\left\lceil\log_2(n!)\right\rceil =\Omega(n\log n).

This lower bound applies to the comparison model. It does not prohibit faster sorting methods under different assumptions, such as methods exploiting bounded integer keys. Merge sort achieves an O(nlog⁡n)O(n\log n) worst-case upper bound, matching the comparison lower bound in asymptotic order.

Establishing a Big-Omega bound

Direct inequalities

The most direct proof supplies suitable constants cc and n0n_0.

For a polynomial with positive leading coefficient,

p(n)=aknk+ak−1nk−1+⋯+a0,ak>0,p(n)=a_kn^k+a_{k-1}n^{k-1}+\cdots+a_0, \qquad a_k>0,

the lower-degree terms eventually have magnitude at most ak2nk\frac{a_k}{2}n^k. Consequently,

p(n)≥ak2nkp(n)\geq \frac{a_k}{2}n^k

for sufficiently large nn, proving p(n)=Ω(nk)p(n)=\Omega(n^k).

Ratio tests

If g(n)>0g(n)>0 eventually, then

f(n)=Ω(g(n))⟺lim inf⁡n→∞f(n)g(n)>0,f(n)=\Omega(g(n)) \quad\Longleftrightarrow\quad \liminf_{n\to\infty}\frac{f(n)}{g(n)}>0,

where the limit inferior may be +∞+\infty.

In particular, if the ordinary ratio limit exists and is positive, whether finite or infinite, it establishes a Big-Omega bound. If the limit is zero, the bound does not hold.

An ordinary limit is not required. For example,

f(n)=n(2+(−1)n)f(n)=n\bigl(2+(-1)^n\bigr)

has f(n)/nf(n)/n alternating between 11 and 33. The ratio does not converge, yet f(n)=Ω(n)f(n)=\Omega(n).

Counting and unavoidable work

Algorithmic lower bounds often arise from work that cannot be avoided under the chosen model. Examples include reading necessary input entries, writing an explicit output, or distinguishing sufficiently many possible answers.

Such arguments require precise assumptions. Producing mm explicit output items requires Ω(m)\Omega(m) output operations in a model where each operation writes only a constant number of items. Returning a compressed representation or a reference to existing data is a different task and need not satisfy the same bound.

Properties and limitations

For eventually nonnegative functions, Big-Omega is transitive:

f=Ω(g),g=Ω(h)⟹f=Ω(h).f=\Omega(g),\qquad g=\Omega(h) \quad\Longrightarrow\quad f=\Omega(h).

Multiplying either function by a fixed positive constant does not change the relation. Changing finitely many function values also has no effect.

Several limitations follow from its asymptotic nature:

  • It does not give exact costs. A statement such as T(n)=Ω(n)T(n)=\Omega(n) specifies neither a concrete running time nor the threshold at which the inequality begins to hold.
  • It need not be tight. Both nn and n3n^3 are in Ω(n)\Omega(n).
  • It requires an eventual uniform bound. Large values on an infinite subsequence are insufficient. A function equal to n2n^2 on even inputs and 11 on odd inputs is not Ω(n)\Omega(n).
  • It depends on the computational model. Treating arbitrary-precision arithmetic as one operation can produce different bounds from counting individual bit operations.
  • It requires a specified limit regime. For several input parameters, a claim such as T(n,m)=Ω(nm)T(n,m)=\Omega(nm) must state which parameter values are included and whether the constants are uniform across them.

Historical conventions

The symbol Ω\Omega has not had a single universal asymptotic meaning. In the Hardy–Littlewood convention used in parts of analytic number theory, f=Ω(g)f=\Omega(g) indicates, roughly, that ff is not asymptotically negligible relative to gg, rather than asserting an eventual positive lower bound.

For positive gg, this convention is commonly formulated through

lim sup⁡x→∞∣f(x)g(x)∣>0.\limsup_{x\to\infty} \left|\frac{f(x)}{g(x)}\right|>0.

It permits substantial values along a subsequence and does not require the computer-science inequality to hold at every sufficiently large argument. The eventual-lower-bound convention was advocated by Donald Knuth and is standard in algorithm analysis. When moving between mathematical fields, the definition in use must therefore be checked rather than inferred from the symbol alone.