Big-Omega notation, written , describes an asymptotic lower bound on the growth of a function. In its standard computer science meaning, states that, beyond some threshold, is at least a positive constant multiple of . 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 and be real-valued functions on the positive integers, with both functions nonnegative for all sufficiently large inputs. Then
if there exist constants and such that
The constants must be independent of . Their existence matters; their precise values usually do not.
For example, let
For every integer ,
Thus , with and . The function also belongs to and : a lower bound need not be the strongest available bound.
Strictly, denotes a set of functions. Consequently,
is the set-theoretic form of the statement. The conventional expression 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 |
|---|---|
| is eventually bounded above by a positive constant multiple of . | |
| is eventually bounded below by a positive constant multiple of . | |
| Both bounds hold, possibly with different constants. | |
| For every positive constant , eventually . |
In particular, Big-O notation and Big-Omega are dual:
A tight asymptotic bound, expressed using Big-Theta notation, satisfies
Little-omega notation is stronger than Big-Omega. For eventually positive ,
Thus , but . By contrast, .
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 be the running time of algorithm on input . Assuming the extrema exist, define
These functions support different claims:
- means that, for every sufficiently large input size, some input requires at least time.
- means that every input of each sufficiently large size requires at least 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 . Its worst-case running time is , and hence also . 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 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 distinct elements, a deterministic algorithm must distinguish among possible input orderings. A binary comparison tree therefore has worst-case height at least
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 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 and .
For a polynomial with positive leading coefficient,
the lower-degree terms eventually have magnitude at most . Consequently,
for sufficiently large , proving .
Ratio tests
If eventually, then
where the limit inferior may be .
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,
has alternating between and . The ratio does not converge, yet .
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 explicit output items requires 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:
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 specifies neither a concrete running time nor the threshold at which the inequality begins to hold.
- It need not be tight. Both and are in .
- It requires an eventual uniform bound. Large values on an infinite subsequence are insufficient. A function equal to on even inputs and on odd inputs is not .
- 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 must state which parameter values are included and whether the constants are uniform across them.
Historical conventions
The symbol has not had a single universal asymptotic meaning. In the Hardy–Littlewood convention used in parts of analytic number theory, indicates, roughly, that is not asymptotically negligible relative to , rather than asserting an eventual positive lower bound.
For positive , this convention is commonly formulated through
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.