Изменения

Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной [[Сортировка|сортировкой]], либо с помощью любой структуры данных, поддерживающей нахождение минимума и удаление за <tex>O(\log n)</tex>, например , [[Двоичная_куча|кучи]]). А так как мы делаем это <tex> n </tex> раз, алгоритм работает за <tex>O(n\log n)</tex>.