Как в учебнике
Пусть при достаточно больших натуральных $n$ выполняются $f(n)\ge0$ и $g(n)>0$. Принадлежность $f\in\Omega(g)$ означает существование постоянных $c>0$ и $n_0$ с $f(n)\ge c g(n)$ для всех $n\ge n_0$.
Это нижняя асимптотическая оценка. Для $f(n)=3n+7$ подходят $c=3$ и $n_0=1$, поскольку $3n+7\ge3n$. Постоянный множитель не обязан быть лучшим: меньший положительный $c$ тоже может работать.
Нижняя оценка не обязана описывать точный порядок. Например, $n^2\in\Omega(n)$, хотя отношение $n^2/n$ не ограничено сверху. Формулировка «не меньше линейного масштаба» не утверждает, что рост ровно линейный.
Символ $\Omega$ не означает лучший случай алгоритма. Сначала выбирают функцию затрат: например, время в худшем случае $T_{\mathrm{worst}}(n)$. К ней уже можно применить нижнюю оценку. Нижняя оценка одного алгоритма также не доказывает, что всякую реализацию задачи невозможно ускорить.
При $g(n)>0$ нижняя оценка требует положительной нижней границы отношения $f(n)/g(n)$ на хвосте. Множитель $c=0$ не подходит: он сделал бы утверждение пустым для любой неотрицательной функции. Например, постоянная функция 7 не принадлежит $\Omega(n)$, поскольку для любого $c>0$ при $n>7/c$ нарушается $7\ge cn$. Проверяется рост, а не просто положительность значений.
Определения и обозначения: Mathematics for Computer Science.
Связанные понятия: O-большое: верхняя оценка роста, Θ-большое: точный порядок роста.
На пальцах
Нижняя оценка ставит пол, ниже которого функция не опускается после выбранного порога. Постоянный множитель может опустить этот пол, но затем он должен удерживать все дальнейшие размеры входа. Для процедуры, обязательно читающей каждый элемент массива, число чтений уже задаёт неизбежную работу в выбранной модели. Один медленный запуск такого доказательства не заменяет: вместе с программой мог проснуться антивирус, а его настроение не устанавливает нижнюю границу.
Пример
Учебная функция $3n+7$ считает условные операции. В каждом случае выделена обязательная линейная часть $3n$.
Ω-большое: нижняя оценка роста
Вход 1
Из десяти операций три уже обеспечивают нижнюю границу.
Шаг 1 из 4: Вход 1
Все шаги текстом
Вход 1
Из десяти операций три уже обеспечивают нижнюю границу.
- n; нижняя граница; затраты
- 13текущий10включён
Вход 2
Линейная часть выросла до 6, общий результат до 13.
- n; нижняя граница; затраты
- 26текущий13включён
Вход 10
Затраты 37 по-прежнему не меньше 30.
- n; нижняя граница; затраты
- 1030текущий37включён
Обоснование хвоста
Неотрицательная добавка 7 делает неравенство верным при каждом n ≥ 1.
- c; n₀
- 3включён1включён
В показанной функции из результата мысленно убирают положительную добавку 7. Оставшиеся $3n$ всегда не больше исходного числа, поэтому это допустимый пол. Значения 3, 6 и 30 меняются вместе с входом, но коэффициент 3 остаётся фиксированным. Для доказательства достаточно любого положительного коэффициента, который работает на всём хвосте; само перечисление трёх проверок такого обещания не даёт.
Нижняя граница относится к объявленной функции и модели. Её нельзя автоматически переносить на все алгоритмы задачи.