Discrete Fourier Transform

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.

Parameters

$n$ : length of the input data set

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 11 of 11 algorithms


Gao’s additive FFT	2010	$O(n \log n \log \log n)$	$O(n)$
Extended Split Radix FFT algorithm	2001	$O(n \log n)$	$O(n)$
Von zur Gathen-Gerhard additive FFT	1996	$O(n (\log n)^2)$	$O(n)$
Wang-Zhu-Cantor additive FFT	1988	$O(n(\log n)^{1.585})$	$O(n)$
Bruun's FFT algorithm	1978	$O(n \log n)$	$O(n)$
Rader–Brenner algorithm	1976	$O(n \log n)$	$O(n)$
Bergland; Glenn radix-8 algorithm	1969	$O(n \log n)$	$O(n)$
Yavne Split Radix FFT algorithm	1968	$O(n \log n)$	$O(n)$
Gentleman; Morven and Gordon Sande radix-4 algorithm	1966	$O(n \log n)$	$O(n)$
Naive algorithm	1965	$O(n^2)$	$O(1)$
Cooley–Tukey algorithm	1965	$O(n \log n)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms