What is Landau notation?

Let $f, g$ be defined near $x_0$ ($x_0 \in \R$ or $\pm\infty$). One writes, as $x \to x_0$:

• $f = o(g)$ (“little-o”) when $f = \varepsilon g$ with $\varepsilon(x) \to 0$;
• $f = O(g)$ (“big-O”) when $f = u g$ with $u$ bounded near $x_0$;
• $f \sim g$ (“equivalent”) when $f = (1 + \varepsilon) g$ with $\varepsilon \to 0$ — equivalently $f - g = o(g)$.

The same notation applies to sequences ($n \to \infty$).