Asymptotic notation (O, o, Ω, Θ)

Landau's symbols compare functions up to constant factors: $f = O(g)$ (grows no faster), $f = \Omega(g)$ (no slower), $f = \Theta(g)$ (same rate), $f = o(g)$ (strictly slower). Born in number theory, adopted by computer science to classify algorithms, and by numerical analysis to measure errors.

Exact running times depend on the machine, the compiler and the input. What survives every change of hardware is the shape of the growth: doubling the input quadruples the time of an $O(n^2)$ algorithm on any computer. Asymptotic notation captures exactly that and throws the rest away.

$f = O(g)$: beyond some point, the graph of $f$ stays under a stretched copy $C\,g$. Big-O is an upper bound, Ω a lower bound, Θ a sandwich. Little-o says the ratio $f/g$ goes to zero — in numerical analysis, $e(h) = o(h)$ means "the error vanishes faster than the step".

For $n \to \infty$ (or $x \to a$):

• $f = O(g) \iff \exists C, n_0:\ |f(n)| \le C\,|g(n)|$ for $n \ge n_0$
• $f = \Omega(g) \iff g = O(f)$
• $f = \Theta(g) \iff f = O(g)$ and $f = \Omega(g)$
• $f = o(g) \iff \lim f(n)/g(n) = 0$

Is $n \log n = O(n^{1.1})$? Yes: $\frac{n\log n}{n^{1.1}} = \frac{\log n}{n^{0.1}} \to 0$, so it is even $o(n^{1.1})$. But the crossover is huge: $\log n = n^{0.1}$ near $n \approx 10^{15}$. Asymptotics tell you who wins eventually, not when.

It is the vocabulary of algorithm design ("this is $O(n \log n)$"), of numerical methods ("Runge–Kutta 4 has error $O(h^4)$"), of Monte Carlo ("error $O(N^{-1/2})$") and of machine learning theory (generalization bounds). One notation, three communities.