Zahl der Operationen beim FFT-Verfahren

• Ist N eine Zweierpotenz ist, so beträgt die Zahl der Operationen (Multiplikationen und Additionen) beim FFT-Verfahren
  • 
• Beweis:
  • Aus der Aufspaltung der Fourierreihe in je eine Fourierreihe für gerade und ungerade Indizes ergab sich die Rekursionsbeziehung
    • 
  • Induktionsanfang:
  • Für N = 1 ist die Fourierreihe einfach
    • X₀ = x₀
  • also gilt
    • ops(1) = 0 = 2*1*log₂(1)
  • Induktionsschritt:
  • Mit der Rekursionsformel und der Induktionsvoraussetzung erhält man durch einfache Rechnung
    •