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

Один алгоритм — разные входы

Количество работы одного и того же алгоритма может зависеть не только от размера входа, но и от самих данных. Например, линейный поиск может найти нужное значение сразу, в середине массива или не найти его вообще.

int index = -1;

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] == target) {
        index = i;
        break;
    }
}

Если target находится в первой ячейке, выполняется одна проверка. Если его нет или он находится в самом конце, придётся просмотреть весь массив. Поэтому для одной и той же длины входа возможны разные затраты.

Лучший и худший случай

Лучший случай описывает наиболее удачный вход данного размера. Для поиска выше это ситуация, когда элемент найден сразу: O(1).

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

Средний случай требует модели

Средний случай пытается описать типичную стоимость по множеству возможных входов. Но слово «средний» само по себе недостаточно: нужно понимать, какие входы возможны и с какой вероятностью они встречаются. Без такой модели средняя оценка может оказаться просто предположением.

Для линейного поиска при естественном допущении, что искомый элемент одинаково вероятно находится в любой позиции, в среднем просматривается доля массива. Постоянный коэффициент отбрасывается, поэтому асимптотическая оценка остаётся O(n).

Всегда называй, какой случай рассматриваешь

Фраза «алгоритм работает за O(n)» может быть недостаточно точной, если его поведение сильно зависит от входа. Иногда в разговоре по умолчанию имеют в виду худший случай, но лучше явно указывать контекст, особенно когда лучший, средний и худший варианты различаются.