Лучший, средний и худший случай

Одна и та же программа может работать за O(1) и за O(n) — всё зависит от данных.

Худший случай — верхняя граница времени работы при самых неудобных входных данных; именно его обычно имеют в виду на собеседовании.

Три сценария

У многих алгоритмов сложность зависит от данных. Линейный поиск элемента в массиве: если искомое стоит первым — O(1) (лучший случай), если последним или отсутствует — O(n) (худший случай), в среднем — O(n/2), то есть O(n).

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

data = [4, 8, 15, 16, 23, 42]
print(linear_search(data, 4))   # лучший: первый же элемент
print(linear_search(data, 42))  # худший: последний
print(linear_search(data, 99))  # худший: не найден

Вывод:

0
5
-1

Почему интервьюер любит худший случай

Худший случай — это гарантия. Когда вы говорите «решение работает за O(n log n)», обычно подразумевается «в худшем случае не хуже». На продакшене данные приходят враждебные: отсортированные наоборот, с дубликатами, пустые. Если вы оцените только средний случай, вас попросят: «А если данные подобраны злонамеренно?»

Как работает под капотом

Средний случай требует модели распределения входов. Для линейного поиска при равновероятном положении искомого среднее число сравнений равно (n+1)/2 — это всё ещё O(n). А вот для быстрой сортировки разница драматична: средний случай O(n log n), но при неудачном выборе опорного элемента (например, всегда крайний на отсортированном массиве) получится O(n^2). Поэтому в реальных реализациях опорный элемент выбирают случайно или по медиане — чтобы худший случай стал маловероятным.

Частые ошибки

Называть средний случай, когда спрашивают про худший — это разные вещи.
Забывать про граничные входы: пустой массив, один элемент, все одинаковые.
Считать, что «обычно быстро» = «гарантированно быстро». Хеш-таблица в среднем O(1), но при коллизиях деградирует.

Итог

Сложность бывает best/average/worst — уточняйте, о каком говорите.
На собеседовании по умолчанию называйте худший случай.
Хорошие алгоритмы делают худший случай маловероятным (рандомизация опорного элемента).