Что такое нотации Big O, Omega и Theta?

Big O описывает верхнюю границу роста («не медленнее, чем»), Omega — нижнюю («не быстрее, чем»), а Theta — точную асимптотику, когда верхняя и нижняя границы совпадают.

Интуиция

• O(n) — при удвоении входа время растёт не более чем линейно.
• Ω(n) — алгоритм не может быть быстрее линейного: например, нужно прочитать все n элементов.
• Θ(n) — рост ровно линейный: функция зажата между двумя линейными оценками.

Пример

Линейный поиск: худший случай O(n), лучший Ω(1) (элемент первый); единой Theta для всех случаев нет, поэтому обычно обсуждают худший случай в терминах Big O.

Детали

• Константы и младшие члены отбрасываются: O(2n + 10) = O(n) — нотация про рост, а не про секунды.
• Классы, которые ждут на собеседовании: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).

Коротко для собеседования

Big O — верхняя оценка роста, Omega — нижняя, Theta — точная, когда они сходятся. На практике обычно называют худший случай в Big O, но всегда уточняйте, о каком случае речь: у quicksort средний O(n log n), а худший O(n²).