Что такое worst case в алгоритмах
Что проверяют
Умеете ли вы рассуждать о стоимости кода не в среднем, а в самом неудобном случае. Для мобильной разработки это прикладной навык: интерфейс живёт в жёстком бюджете кадра, и один редкий тяжёлый вызов на главном потоке пользователь видит как рывок, даже если в среднем всё быстро.
Как отвечать
Worst case это верхняя граница стоимости по всем входам данного размера: сколько операций алгоритм сделает на самом неудачном наборе. Рядом стоят средний случай (ожидание по распределению входов) и амортизированный (усреднение по последовательности операций, а не по входам).
Примеры, которые полезно назвать: быстрая сортировка даёт O(n log n) в среднем и O(n^2) на неудачном опорном элементе, поэтому его выбирают случайно; хеш-таблица даёт O(1) в среднем и O(n) при совпадении хешей; добавление в конец динамического массива амортизированно O(1), но отдельная вставка с перевыделением это O(n).
В Swift есть свои острые места. Индексация строки не константная, потому что Character это графемный кластер, и обход по index(_:offsetBy:) в цикле легко превращается в квадратичный. Массив копируется при записи, если на буфер есть вторая ссылка, и безобидная мутация становится O(n) на каждой итерации.
Где спотыкаются
Ставят знак равенства между O-нотацией и худшим случаем. Это разные вещи: нотация описывает рост функции, и оценивать через неё можно любой случай, включая средний. Путаница вылезает сразу, когда просят назвать в тех же терминах средний.
Отчитываются амортизированной оценкой там, где важна одна операция. Для пропускной способности среднее честно, для отрисовки кадра нет: перевыделение буфера случится именно в этом кадре, и спасает предварительное резервирование ёмкости.
Отмахиваются от худшего случая как от невероятного. Он приходит не случайно, а от данных: отсортированный вход, совпадающие ключи, откат регулярного выражения на длинной строке. Такие наборы прилетают из сети и от пользователя, то есть контролируете их не вы.