Big-Theta notation, written , describes functions that grow at the same rate up to positive constant factors as their argument becomes sufficiently large. In computer science, it is used to express tight bounds on the resources required by an algorithm, especially running time and memory. A statement such as means that, beyond some input size, is bounded both above and below by positive constant multiples of . It does not specify an exact running time or require the ratio to approach a limit.
Formal definition
Let and be real-valued functions of a positive integer , with both functions nonnegative for all sufficiently large . The set consists of all functions for which there exist constants , , and such that
The constants must be independent of , though they may depend on the particular functions being compared.
The lower inequality prevents from becoming arbitrarily small relative to ; the upper inequality prevents it from becoming arbitrarily large relative to . Both must hold for every sufficiently large argument, not merely for infinitely many arguments.
Strictly speaking, the notation expresses membership in a set of functions:
The conventional form
uses the equals sign as shorthand for this membership relation. It should not be interpreted as ordinary equality between a function and a set.
For functions that can take negative values, an absolute-value definition is also used:
for all sufficiently large . In algorithm analysis, resource counts are normally nonnegative, so the nonnegative definition is usually sufficient.
Relationship to other asymptotic notations
Big-Theta is part of asymptotic analysis, which studies limiting behavior rather than exact values at every argument.
The two bounds in its definition correspond to two other notations:
- Big-O notation, , gives an asymptotic upper bound.
- Big-Omega notation, , gives an asymptotic lower bound.
Under the same nonnegativity assumptions,
Thus, a Theta bound is asymptotically tight: its upper and lower bounds agree up to constant factors.
For example, is correct, but it is not tight. The statement is false because no positive constant multiple of remains below for all sufficiently large .
Theta versus asymptotic equivalence
Asymptotic equivalence, written , usually means
This is stronger than a Theta relationship. For instance,
but , even though .
More generally, if
then . A limit is sufficient, however, not necessary. The ratio can oscillate while staying between positive constants.
Examples and proof methods
Polynomial growth
Consider
For , both and , so
Choosing , , and proves
In general, a polynomial with positive leading coefficient has the same asymptotic order as its highest-degree term. Lower-degree terms and fixed multiplicative constants do not change its Theta class.
Counting repeated operations
Suppose an algorithm performs a constant-time operation times during outer-loop iteration , for . The total operation count is
This illustrates why nested loops do not have to execute the same number of inner iterations to yield quadratic growth. The relevant quantity is the total number of operations.
Logarithmic growth
For fixed bases ,
Because the conversion factor is a positive constant,
Consequently, the logarithm’s base is often omitted in asymptotic resource bounds. This simplification does not apply to exponential bases: and are not Theta-equivalent.
Oscillation
For positive integers , let
Its value is either or , so
Therefore , even though has no limit. Theta notation describes bounded relative growth, not convergence to a fixed ratio.
Use in algorithm analysis
In computational complexity, Theta notation commonly describes time complexity and space complexity as functions of input size.
Typical examples include:
| Algorithm or operation | Tight bound | Assumptions |
|---|---|---|
| Accessing an element of an [[array-data-structure | array]] by index | |
| [[binary-search | Binary search]] | worst-case comparisons |
| [[merge-sort | Merge sort]] | worst-case time |
| [[insertion-sort | Insertion sort]] | worst-case time |
The resource and computational model matter. An arithmetic operation on fixed-size machine words may be treated as constant time, whereas arithmetic on arbitrarily large integers generally depends on the number of bits involved.
Worst case, average case, and amortized cost
Theta notation does not itself specify which inputs or executions are being analyzed.
For an algorithm whose running time on input is , a worst-case function can be defined as
A statement tightly bounds that maximum. It does not say that every input of size takes time.
An average-case bound concerns an expected value under a specified distribution of inputs. For a randomized algorithm, an expected bound may instead concern the algorithm’s internal random choices. These are different sources of randomness and must be identified.
In amortized analysis, a bound concerns the cost of a sequence of operations, rather than necessarily the cost of each operation individually. Appending to a dynamic array with geometric capacity growth can take time when a resize copies existing elements, while having amortized cost per append.
Algebraic properties
For eventually positive functions, having the same Theta class is an equivalence relation:
- Reflexivity: .
- Symmetry: if , then .
- Transitivity: if and , then .
Useful calculation rules include the following.
For a positive constant ,
For eventually nonnegative and ,
If and , with all functions eventually positive, then
and
Subtraction requires care because cancellation can remove the dominant term. Knowing that and does not determine the order of . For example, if and , then .
Scope and limitations
Theta notation deliberately discards constant factors and finite initial behavior. Two implementations in the same Theta class may differ greatly in actual running time because of memory access patterns, hardware, compiler optimizations, or large hidden constants. An asymptotically slower algorithm can outperform another over a practically relevant range of input sizes.
A Theta bound also does not establish that an algorithm is optimal. An algorithm with running time has a tight description of its own growth; proving optimality requires a suitable lower bound for all algorithms solving the problem within the stated model.
Input size must be defined carefully. If an integer has numerical value , its binary representation has length . A running time linear in is therefore exponential in that representation length.
For functions of several variables, the domain and quantifiers must also be specified. In a bound such as , the multiplicative constants must be uniform over the stated range of and . Treating one parameter as fixed can produce a different claim from allowing both to vary independently.