Big O — нотация сложности алгоритмов, описывает рост ресурсов (время/память) относительно размера входа n.

• Типовые: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n).

• Указывает верхнюю границу в худшем случае; есть и другие нотации (Θ, Ω).

• Скрывает константы, важно для сравнения асимптотик при больших n.

• Практика: анализ критических путей, выбор структур данных и алгоритмов с учетом реальных ограничений.

Примеры:

• Поиск в отсортированном массиве (бинарный) — O(log n).

• Хеш-таблица (успех) — O(1) амортизированно; в худшем при коллизиях — O(n).

• Сортировка слиянием — O(n log n); пузырьковая — O(n^2).