Asymptotics

Asymptotics describe the relation of two functions as their inputs grow. The table below shows the formal definitions as well as the operator intuitively corresponding to the asymptotic behavior.

Orders describe the behavior of two functions only up to a constant factor. So for example

4n \in O(n)

. Similarly, it only matters that the relation holds after some constant

M

, so

1000 + n \in O(n)

| *Definition* | *Limit Test* | ||
$f \sim g$ | $\to$ | \(\lim_{x \to \infty} \frac{f(x)}{g(x)} = 1\) | $=$ ||
$f \in O(g)$ | $\exists c. \exists M. \forall x > M. \lvert f(x)\rvert \le cg(x)$ | \(\lim_{x \to \infty} \frac{\lvert f(x)\rvert}{g(x)} \in \R\) | $\leq$ ||
$f \in o(g)$ | $\to$ | \(\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\) | $<$ ||
$f \in \Omega(g)$ | $g \in O(f)$ | \(\lim_{x \to \infty} \frac{f(x)}{g(x)}  \in (0, \infty]\) | $\ge$ ||
$f \in \omega(g)$ | $g \in o(f)$ | \(\lim_{x \to \infty} \frac{f(x)}{g(x)}  = \infty\) | $>$ ||
$f \in \Theta(g)$ | $f \in O(g)$ and $g \in O(f)$ | \(\lim_{x \to \infty} \frac{f(x)}{g(x)}  \in (0, \infty)\) | $=$