===Время работы===
В итоге мы получили алгоритм выполняющий С помощью метода потенциалов можно показать, что время работы <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>.
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.
