# Wikenigma - an Encyclopedia of Unknowns Wikenigma - an Encyclopedia of the Unknown

# FFT bounds

A *Fast Fourier Transform* (FFT) is well established computational / mathematical method for calculating the *Discrete Fourier Transform* (DFT) of a dataset. That's to say, which simple harmonic frequencies, in which ratios, can be combined to approximate a complex varying signal (i.e. waveform).

FFT is a widely used essential tool in signal analysis - in fields such as communications, audio processing, radar, orbital calculations etc. etc. .

The original DFT was discovered in the early 1800s, but the complexity of the calculations led to the development, mainly in the mid 1900s, of a special versions, called FFT, which greatly simplified the mathematical work involved - sometimes by a factor of more than 1,000.

The number of calculations required - known as the 'bounds' - is still substantial, and a goal is to define the minimum number necessary, and if possible improve the current methods.

The lower bounds are currently unknown. Formally stated : Can they be faster than $${\displaystyle O(N\log N)}$$

- where *O* is the computational load, and* N* is the size of the dataset.

**Show another (random) article**

Suggestions for corrections and ideas for articles are welcomed :

**Get in touch!**

Further resources :