Изменения

С помощью [[Амортизационный анализ|метода потенциалов]] можно показать, что время работы <tex>O(n)</tex>. Потенциал величины <tex>k</tex> связывается с текущим ее значением в алгоритме. Начальное значение этого потенциала равно нулю. На каждой итерации цикла <tex>while</tex> значение <tex>k</tex> уменьшается, поскольку <tex>\pi(k) < k</tex>. Поскольку <tex>\pi(k) \ge 0</tex> значение этой переменной не бывает отрицательным. Также значение <tex>k</tex> изменяется не более чем на 1 внутри тела цикла <tex>for</tex>. Поскольку перед входом в цикл выполняется <tex> k < i</tex> и поскольку значение переменной <tex>i</tex> увеличивается в каждой итерации цикла <tex>for</tex>, справедливость неравенства <tex>k < i</tex> сохраняется (подтверждая тот факт, что соблюдается также неравенство <tex>\pi(i) < i </tex>. Каждое выполнение тела цикла <tex>while</tex> можно оплатить соответствующим уменьшение потенциальной функции, поскольку <tex>\pi(k) < k </tex>. Кроме этого значение потенциальной функции возрастает не более чем на 1, из-за этого [[Амортизационный анализ|амортизированная стоимость ]] тела цикла <tex>for</tex> {{---}} <tex>O(1)</tex>. Так как количество итераций <tex>O(n)</tex>, и поскольку конечное значение потенциальной функции по величине не меньше, чем ее начальное значение, полное время работы в наихудшем случае равно <tex>O(n)</tex>.