CLRS-Lean
CLRS Fourth Edition
Chapter 30. Polynomials and the FFT
30.2. The DFT and FFT
30.2. Recursive Radix-2 FFT

Imports

import CLRSLean.FourthEdition.Chapter_30.Section_30_2_DFT_And_FFT.RecursiveFFT.Definitions
import CLRSLean.FourthEdition.Chapter_30.Section_30_2_DFT_And_FFT.RecursiveFFT.Correctness
import CLRSLean.FourthEdition.Chapter_30.Section_30_2_DFT_And_FFT.RecursiveFFT.Costs

Section 30.2 - Recursive radix-2 FFT

The recursive FFT surface is split into the value-producing execution, its equality with the generic DFT and inverse, and execution-derived exact and padded all-input costs.

Implementation pages:

Definitions and execution
Correctness and inverse
Exact and padded costs

              namespace CLRSnamespace Chapter30end Chapter30end CLRS