02.02.059 Формальные определения асимптотических обозначений - justjune/AiSD2026 GitHub Wiki

Наихудший случай $f(n) = O(g(n))$ означает, что функция $f(n)$ ограничена сверху функцией $c \cdot g(n)$.
Формально: $\exists$ константа $c$ и натуральное $n_0$, что $f(n) \le c \cdot g(n) \quad \forall n \ge n_0$. (Рис. 2.3, а).

Наилучший случай $f(n) = \Omega(g(n))$ означает, что функция $f(n)$ ограничена снизу функцией $c \cdot g(n)$.
Формально: $\exists$ константа $c$ и натуральное $n_0$, что $f(n) \ge c \cdot g(n) \quad \forall n \ge n_0$. (Рис. 2.3, б).

Средний случай $f(n) = \Theta(g(n))$ означает, что функция $f(n)$ ограничена сверху и ограничена снизу одной и той же функцией $g(n)$, но с разными множителями: сверху $c_1 \cdot g(n)$ и снизу $c_2 \cdot g(n)$.
Формально: $\exists$ константы $c_1$, $c_2$ и натуральное $n_0$, что $c_2 \cdot g(n) \le f(n) \le c_1 \cdot g(n) \quad \forall n \ge n_0$. (Рис. 2.3, в).