(см. скан)
Процедура предусматривает обращение к самой себе при 
а при 
— использование следующих формул:
Совершенно очевидно, что последовательное деление 
пополам можно реализовать лишь в случае, когда 
есть некоторая степень числа 2, и только для таких значений существует простой алгоритм БПФ. Кроме того, уравнением 
можно воспользоваться для определения трудоемкости вычислительной процедуры. Пусть 
— трудоемкость для случая 
отсчетов. Кроме затрат на вычисление значений двух фурье-образов, входящих в правую часть уравнения 
само оно требует затрат, пропорциональных значению 
и связанных с умножением на показательную функцию и последующим сложением. Если с — постоянная, характеризующая трудоемкость этих операций, то С 
определяется следующим уравнением:
Аналогичным образом находим, что
где 
— число таких уравнений; 
в частности, равно числу членов ряда 
которое равно 
минус 1. В таком случае уравнение 
принимает вид
и т. д. Из уравнений 
следует, что 
эквивалентно трудоемкости двух сложений, которую обозначим через с. Если выписать уравнения, аналогичные 
для 
где 
умножить каждое из них на 
затем сложить с уравнением 
и далее с уравнением 
умноженным на два, то оказывается, что второй член в правой части которого представляет величины, линейно пропорциональные 
