Что такое асимптотическая сложность O-большое и Omega-большое

Что проверяют

Владеете ли вы языком оценок, а не одним заученным словом. В работе с данными это рабочий инструмент: прикинуть, во что обойдётся обучение или запрос на миллионе объектов, нужно до того, как задача уедет на кластер и займёт там ночь.

Как отвечать

Начните с определений, они короткие.

Функция f принадлежит O(g), если найдутся c > 0 и порог n0 такие, что f(n) <= c*g(n) для всех n >= n0. Это верхняя граница роста.

Принадлежность Omega(g) означает то же самое с обратным неравенством: f(n) >= c*g(n). Это нижняя граница.

Если верны обе оценки сразу, пишут Theta(g), и это самое информативное утверждение.

На примере: для f(n) = 3n^2 + 5n + 2 верно и f = O(n^2), и f = Omega(n^2), значит f = Theta(n^2). Заметьте, что f = O(n^3) формально тоже верно, просто бесполезно.

Дальше проговорите главное: граница и случай это разные оси. Можно сказать, что быстрая сортировка в лучшем случае Theta(n log n), а в худшем Theta(n^2). Отдельно существуют нижние оценки самой задачи, а не алгоритма: сортировке сравнениями нужно Omega(n log n) сравнений, и никакой алгоритм этот барьер не обойдёт.

Где спотыкаются

Ставят знак равенства между O и худшим случаем, а между Omega и лучшим. Это независимые измерения: верхнюю и нижнюю оценку можно записать для любого случая, и фраза про лучший случай O(n) вполне корректна.

Называют оценку и не уточняют, что такое n и что считается элементарной операцией. В задачах с данными это критично: сложность по числу объектов, по размерности признаков и по числу эпох ведёт себя по-разному, а память нередко упирается раньше времени.

Забывают про константы и реальные размеры. Асимптотика описывает поведение на бесконечности, а на рабочем объёме выигрывает алгоритм с меньшим множителем, лучшей локальностью по памяти и векторизацией.