Fast Fourier Transform

Cooley–Tukey radix-2 FFT splits a sequence into even and odd sub-problems then merges with twiddle factors to drop DFT cost from O(n^2) to O(n log n).

Time Complexity

O(n log n)

Even / odd recursion

Space Complexity

O(n)

Aux arrays or in-place

Core Pattern

Butterfly Merge

Twiddle factor combine

Key Mechanics

Frequency Domain

Transforms time-domain samples into frequency spectrum.

Convolution Power

Fast polynomial & signal convolution via pointwise multiply.

Butterflies

Pair operations reuse partial sums / differences.

Core Uses

Spectral analysis (DSP).
Fast convolution / polynomial multiplication.
Compression & filtering (e.g. audio/image transforms).
Numerical methods & PDE solving.

Recurrence

T(n) = 2T(n/2) + O(n)

Master Theorem => O(n log n). Linear twiddle merge dominates after two sub-transforms.

Deep Theory Interactive Simulation

Strassen's Matrix Multiplication Karatsuba Multiplication