Какова временная сложность решения в нотации O

Что проверяют

Умеете ли вы оценить свой код на Swift с учётом скрытой стоимости стандартной библиотеки и связываете ли асимптотику с отзывчивостью интерфейса. Следом обычно спрашивают, как ускорить решение и что будет, если выполнить его на главном потоке.

Как отвечать

Назовите, что такое n, пройдите по коду и сложите стоимость шагов: последовательные складываются, вложенные перемножаются, в итоге остаётся старший член. Главное здесь знать цену операций в Swift, её пишут в документации в разделе «Complexity»:

• Array: доступ по индексу O(1), append амортизированно O(1), insert(_:at:) в начало, removeFirst() и contains O(n);
• Set и Dictionary: вставка, поиск и удаление O(1) в среднем, поэтому проверку вхождения в цикле переносят сюда;
• sort() и sorted(): O(n log n);
• String: не коллекция с произвольным доступом. count проходит всю строку по графемам и стоит O(n), сдвиг индекса через index(_:offsetBy:) тоже O(n);
• copy-on-write: присваивание массива бесплатное, но первое изменение копии дублирует весь буфер за O(n).

Итог сформулируйте вместе с памятью: «O(n log n) по времени, O(n) по памяти на отсортированную копию».

Для iOS добавьте практический вывод. Кадр при 60 Гц это около 16 мс, на экранах ProMotion со 120 Гц около 8 мс. Квадратичная фильтрация тысячи элементов в cellForRowAt или в body у SwiftUI, который пересчитывается при каждом изменении состояния, заметна глазом. Тяжёлые вычисления уносят с главного потока в Task.detached или на фоновую очередь и кешируют результат.

Где спотыкаются

Вызывают string.count или сдвигают индекс строки на число внутри цикла. Каждый шаг линейный, и безобидный цикл превращается в O(n²).

Проверяют array.contains в цикле по другому массиву и получают O(n·m), хотя Set сделал бы решение линейным.

Внутри цикла копируют большой массив в var и меняют в копии один элемент. Каждая такая первая запись дублирует весь буфер, и цикл неожиданно становится квадратичным и по времени, и по нагрузке на память.