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

Big-Theta Notation

Big-Theta notation describes an asymptotically tight bound on a function’s growth, ignoring constant factors and behavior on sufficiently small inputs.

20 keywords2 linked from2 not yet writtenWritten by AI
Computer ScienceAlgorithmFunction (mathem…Big-O NotationBig-Omega Notati…PolynomialComputational Co…Time ComplexityBig-Theta…

Big-Theta notation, written Θ\Theta, 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 T(n)=Θ(n2)T(n)=\Theta(n^2) means that, beyond some input size, T(n)T(n) is bounded both above and below by positive constant multiples of n2n^2. It does not specify an exact running time or require the ratio T(n)/n2T(n)/n^2 to approach a limit.

Formal definition

Let ff and gg be real-valued functions of a positive integer nn, with both functions nonnegative for all sufficiently large nn. The set Θ(g(n))\Theta(g(n)) consists of all functions ff for which there exist constants c1>0c_1>0, c2>0c_2>0, and n0n_0 such that

0≤c1g(n)≤f(n)≤c2g(n)for every n≥n0.0\leq c_1g(n)\leq f(n)\leq c_2g(n) \qquad\text{for every }n\geq n_0.

The constants must be independent of nn, though they may depend on the particular functions being compared.

The lower inequality prevents ff from becoming arbitrarily small relative to gg; the upper inequality prevents it from becoming arbitrarily large relative to gg. 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:

f∈Θ(g).f\in\Theta(g).

The conventional form

f(n)=Θ(g(n))f(n)=\Theta(g(n))

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:

c1∣g(n)∣≤∣f(n)∣≤c2∣g(n)∣c_1|g(n)|\leq |f(n)|\leq c_2|g(n)|

for all sufficiently large nn. 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, f(n)=O(g(n))f(n)=O(g(n)), gives an asymptotic upper bound.
  • Big-Omega notation, f(n)=Ω(g(n))f(n)=\Omega(g(n)), gives an asymptotic lower bound.

Under the same nonnegativity assumptions,

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)).

Thus, a Theta bound is asymptotically tight: its upper and lower bounds agree up to constant factors.

For example, n2=O(n3)n^2=O(n^3) is correct, but it is not tight. The statement n2=Θ(n3)n^2=\Theta(n^3) is false because no positive constant multiple of n3n^3 remains below n2n^2 for all sufficiently large nn.

Theta versus asymptotic equivalence

Asymptotic equivalence, written f(n)∼g(n)f(n)\sim g(n), usually means

lim⁡n→∞f(n)g(n)=1.\lim_{n\to\infty}\frac{f(n)}{g(n)}=1.

This is stronger than a Theta relationship. For instance,

3n2∼3n2+n,3n^2\sim 3n^2+n,

but 3n2≁n23n^2\not\sim n^2, even though 3n2=Θ(n2)3n^2=\Theta(n^2).

More generally, if

lim⁡n→∞f(n)g(n)=L,0<L<∞,\lim_{n\to\infty}\frac{f(n)}{g(n)}=L, \qquad 0<L<\infty,

then f(n)=Θ(g(n))f(n)=\Theta(g(n)). A limit is sufficient, however, not necessary. The ratio can oscillate while staying between positive constants.

Examples and proof methods

Polynomial growth

Consider

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

For n≥1n\geq1, both n≤n2n\leq n^2 and 1≤n21\leq n^2, so

3n2≤3n2+5n+7≤15n2.3n^2\leq 3n^2+5n+7\leq15n^2.

Choosing c1=3c_1=3, c2=15c_2=15, and n0=1n_0=1 proves

3n2+5n+7=Θ(n2).3n^2+5n+7=\Theta(n^2).

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 ii times during outer-loop iteration ii, for i=1,…,ni=1,\ldots,n. The total operation count is

∑i=1ni=n(n+1)2=Θ(n2).\sum_{i=1}^{n}i=\frac{n(n+1)}{2}=\Theta(n^2).

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 a,b>1a,b>1,

log⁡an=log⁡bnlog⁡ba.\log_a n=\frac{\log_b n}{\log_b a}.

Because the conversion factor is a positive constant,

log⁡an=Θ(log⁡bn).\log_a n=\Theta(\log_b n).

Consequently, the logarithm’s base is often omitted in asymptotic resource bounds. This simplification does not apply to exponential bases: 2n2^n and 3n3^n are not Theta-equivalent.

Oscillation

For positive integers nn, let

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

Its value is either nn or 3n3n, so

n≤f(n)≤3n.n\leq f(n)\leq3n.

Therefore f(n)=Θ(n)f(n)=\Theta(n), even though f(n)/nf(n)/n 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 Θ(1)\Theta(1)
[[binary-search Binary search]] Θ(log⁡n)\Theta(\log n) worst-case comparisons
[[merge-sort Merge sort]] Θ(nlog⁡n)\Theta(n\log n) worst-case time
[[insertion-sort Insertion sort]] Θ(n2)\Theta(n^2) 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 xx is T(x)T(x), a worst-case function can be defined as

Tworst(n)=max⁡∣x∣=nT(x).T_{\mathrm{worst}}(n)=\max_{|x|=n}T(x).

A statement Tworst(n)=Θ(g(n))T_{\mathrm{worst}}(n)=\Theta(g(n)) tightly bounds that maximum. It does not say that every input of size nn takes Θ(g(n))\Theta(g(n)) 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 Θ(n)\Theta(n) time when a resize copies nn existing elements, while having amortized Θ(1)\Theta(1) cost per append.

Algebraic properties

For eventually positive functions, having the same Theta class is an equivalence relation:

  • Reflexivity: f=Θ(f)f=\Theta(f).
  • Symmetry: if f=Θ(g)f=\Theta(g), then g=Θ(f)g=\Theta(f).
  • Transitivity: if f=Θ(g)f=\Theta(g) and g=Θ(h)g=\Theta(h), then f=Θ(h)f=\Theta(h).

Useful calculation rules include the following.

For a positive constant aa,

af=Θ(f).af=\Theta(f).

For eventually nonnegative ff and gg,

f+g=Θ(max⁡{f,g}).f+g=\Theta(\max\{f,g\}).

If f1=Θ(g1)f_1=\Theta(g_1) and f2=Θ(g2)f_2=\Theta(g_2), with all functions eventually positive, then

f1f2=Θ(g1g2),f_1f_2=\Theta(g_1g_2),

and

f1f2=Θ ⁣(g1g2).\frac{f_1}{f_2}=\Theta\!\left(\frac{g_1}{g_2}\right).

Subtraction requires care because cancellation can remove the dominant term. Knowing that f=Θ(n2)f=\Theta(n^2) and g=Θ(n2)g=\Theta(n^2) does not determine the order of f−gf-g. For example, if f(n)=n2+nf(n)=n^2+n and g(n)=n2g(n)=n^2, then f(n)−g(n)=nf(n)-g(n)=n.

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 Θ(n2)\Theta(n^2) 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 NN, its binary representation has length Θ(log⁡N)\Theta(\log N). A running time linear in NN 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 Θ(n+m)\Theta(n+m), the multiplicative constants must be uniform over the stated range of nn and mm. Treating one parameter as fixed can produce a different claim from allowing both to vary independently.