По какому времени работает функция reduce у массива

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

Понимаете ли вы, что асимптотика складывается из числа итераций и стоимости одного шага. Правильный ответ про reduce в Swift состоит из двух частей, и вторая отсеивает тех, кто выучил O(n) как готовый факт.

Как отвечать

reduce проходит последовательность один раз и вызывает замыкание для каждого элемента, значит число вызовов линейно, O(n). Но общая сложность это O(n), умноженное на стоимость шага, а стоимость шага задаёте вы сами.

Для суммы чисел шаг константный, итог линейный. Для накопления коллекции всё меняется: обычная форма принимает аккумулятор по значению и возвращает новый, поэтому склейка массива или пересборка словаря на каждом шаге даёт копию и квадратичное поведение.

// O(n^2): на каждом шаге создаётся новый массив
let bad = items.reduce([Int]()) { $0 + [$1 * 2] }

// O(n): аккумулятор меняется на месте
let good = items.reduce(into: [Int]()) { $0.append($1 * 2) }

reduce(into:) передаёт аккумулятор как inout, копирование при записи не срабатывает, лишних копий нет. Добавьте, что reduce не умеет прерываться досрочно: для поиска первого подходящего элемента нужен first(where:), для проверки условия contains(where:), иначе вы платите за полный проход там, где хватило бы половины.

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

Отвечают O(n) и замолкают. Это верно про число вызовов замыкания и неверно про алгоритм целиком: собранные через reduce массив, строка или словарь легко превращают линейный проход в квадратичный.

Второе: не знают про reduce(into:). Именно его спрашивают следом, и это же главный практический вывод: накапливаете коллекцию, берите форму с into.

Третье: отвечают про JavaScript. Вопрос задан на собеседовании по iOS, речь о reduce из протокола Sequence с его правилами копирования значений, а рассказ про метод массива в браузере показывает, что кандидат пересказывает статью, а не свой опыт.