Editing Fast Fourier Transform
Warning: You are not logged in.Your IP address will be recorded in this page's edit history.
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
|Latest revision||Your text|
|Line 1:||Line 1:|
'''Fast Fourier ''' ('''FFT''') is an efficient algorithm for calculating the [[DFT|discrete fourier transform]] (DFT). The FFT produces the same results as a DFT but it reduces the execution time by hundreds in some cases. Whereas DFT takes an order of <math>O(n^2)\,</math> computations, FFT takes an order of <math>O(n\,\log\,n)</math>, and is definitely the preferred algorithm to be used in all applications in terms of computational complexity. The FFT in most implementations consistent of samples that are exactly a power of 2, this is commonly known as a ''FFT Radix 2'' algorithm where <math> n = 64,128,256,512,1024,2048</math> etc.