Big-Θ notation

Big-Θ notation (or big theta notation) is used to describe the growth rate of a pattern when the actual formula f(t) for the growth is complex but, over time, becomes effectively the same as a simpler formula g(t). It is said that f(t) is proportional to g(t) or, even more simply, the pattern grows like g(t). This is expressed in big-Θ notation as f(t) is Θ(g(t)). In essence, g sheds details of f which might otherwise obscure understanding of what happens as t gets large.

For example, the population of the spacefiller max, p(t), can be expressed as follows:

• p(t) = t²4 + 21*t2 + 209, if t ≡ 0 (mod 4)
• p(t) = t²4 + 21*t2 + 215, if t ≡ 2 (mod 4)
• p(t) = t²4 + 10*t + 9234 otherwise

As t gets large, the t²/4 term dominates. In other words, the population of max grows like t²/4, or p(t) is Θ(t²) or p(t) is Θ(t²/4).

Other asymptotic notations

See also Limit inferior and limit superior and big O notation at Wikipedia

• infm≥n(f(m)): f's minimum over all inputs greater than or equal to n.
• supm≥n(f(m)): like inf but f's maximum instead.

Where they are defined (when limits of functions' minima and maxima exist), inf is an increasing function of n, and sup a decreasing one.

• lim infn->∞(f(n)), lim supn->∞(f(n)): The limit that inf and sup approach when evaluated on arbitrarily large inputs.

These may be used to rigorously define the other notations.

• Small O notation: f(n) is o(g(n)) if f's growth is less than g's

limn->∞(f(n)g(n)) = 0

• Big O notation: f(n) is O(g(n)) if f's growth is less than or equal to g's

lim supn->∞(f(n)g(n)) < ∞

The limit may be finite or zero.

• Big omega notation: f(n) is Ω(g(n)) if f's growth is greater than or equal to g's

lim infn->∞(f(n)g(n)) > 0

The limit may be finite or infinite.

• Small omega notation: f(n) is ω(g(n)) if f's growth is greater than g's

limn->∞(f(n)g(n)) = ∞

With these definitions, f(n)=Θ(g(n)) iff f(n)=O(g(n)) and f(n)=Ω(g(n)), in the same manner that x=y iff x≤y and x≥y.

Further reading

• Nathaniel Johnston, Dave Greene. Conway's Game of Life: Mathematics and Construction (2022), A.3. Appendix A: Big-Θ Notation