Big-Theta Notation

Big-Theta notation gives a tight bound: the function grows at exactly the stated rate, up to constants.

A two-sided bound

f(n) = Theta(g(n)) means f is bounded both above and below by constant multiples of g for large n. It combines big-O and big-Omega: the growth rate is pinned down exactly, not just capped or floored.

Formal definition

f(n) = Theta(g(n)) if there exist positive constants c1, c2, and n0 such that c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0. Equivalently, f = O(g) and f = Omega(g) simultaneously.

When to use it

Use Theta when you can prove matching upper and lower bounds. Merge sort is Theta(n log n): it never does more than a constant times n log n comparisons, and comparison sorting cannot do fewer. That is a complete characterization, stronger than either one-sided claim alone.

Why people say O when they mean Theta

In casual usage "this algorithm is O(n log n)" often means Theta. Strictly, O only promises an upper bound, so an O(n^2) algorithm might secretly be linear. When precision matters, especially in proofs and lower-bound arguments, reserve Theta for tight results and O for upper bounds you have not shown are tight.

• Theta implies both O and Omega
• A Theta bound is the sharpest of the three
• Not every function has a simple Theta form; some oscillate between rates

A quick check

To confirm f(n) = Theta(g(n)), it often suffices to show the limit of f(n)/g(n) as n grows is a positive finite constant. If that ratio settles to a nonzero number, the two functions grow at the same rate and the Theta relation holds.