Big Theta

The notion of asymptotic growth can be used to partition the space of functions.

Two functions f(n) and g(n) are ``equal'' if neither is asymptotically bigger than the other. We write this as $f(n) = \Theta(g(n))$.

Formally, $f(n) = \Theta(g(n))$ if and only if there exists scaling factors c₁ and c₂ and threshold n₀ such that $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$.

It's an f(n) sandwich on g(n) bread!