О-символика

$f(n) = O(g(n))$, если существуют $n_0 \in \mathbb{N}, C > 0\mathpunct{:}~~ |f(n)| \le C|g(n)|$ для всех $n > n_0$. Или $\limsup\limits_{n \to \infty} \left|\dfrac{f(n)}{g(n)}\right| < \infty$.

$f(n) = o(g(n))$, если для любого $C > 0$ существует $n_0 \in \mathbb{N}\mathpunct{:}~~ |f(n)| \le C|g(n)|$ для всех $n > n_0$. Или $\lim\limits_{n \to \infty} \left|\dfrac{f(n)}{g(n)}\right| = 0$.

$f(n) = \Omega(g(n))$, если существуют $n_0 \in \mathbb{N}, C > 0\mathpunct{:}~~ |f(n)| \ge C|g(n)|$ для всех $n > n_0$. Или $\liminf\limits_{n \to \infty} \left|\dfrac{f(n)}{g(n)}\right| > 0$.

$f(n) = \Theta(g(n))$, если $f(n) = O(g(n))$ и $f(n) = \Omega(g(n))$. Или существуют $C_1, C_2 > 0$ такие, что $C_1 \le \liminf\limits_{n \to \infty} \left|\dfrac{f(n)}{g(n)}\right|$ и $\limsup\limits_{n \to \infty} \left|\dfrac{f(n)}{g(n)}\right| \le C_2$.

В записях вида $f(n) = O(g(n))$ знак $=$ **внезапно** не означает равенства. Иначе $n = O(n^2)$ и $n^2 = O(n^2)$ повлечет $n = n^2$.