The most common FFT is the '''Cooley-Tukey''' algorithm. In its most basic form, this method first computes the Fourier transforms of the even-indexed numbers ''x''<sub>0</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''-2</sub>, and of the odd-indexed numbers ''x''<sub>1</sub>, ''x''<sub>3</sub>,. ..., ''x''<sub>''n''-1</sub>, and then combines those two results to produce the Fourier transform of the whole sequence. This idea can then be performed [[recursion|recursively]] to reduce the overall runtime to O(''n'' log ''n''). This simplified form assumes that ''n'' is a power of two; since the number of sample points ''n'' can usually be chosen freely by the application, this is often not an important restriction.
We write ''n''<nowiki>'</nowiki> = ''n''/2 and denote the DFT of the even-indexed numbers ''x''<nowiki>'</nowiki><sub>0</sub> = ''x''<sub>0</sub>, ''x''<nowiki>'</nowiki><sub>1</sub> = ''x''<sub>2</sub>,. ..., ''x''<nowiki>'</nowiki><sub>''n''<nowiki>'</nowiki>-1</sub> = ''x''<sub>''n''-2</sub> by ''f''<sub>0</sub>', ..., ''f'' <nowiki>'</nowiki><sub>''n''<nowiki>'</nowiki>-1</sub>,; and the DFT of the odd-indexed numbers ''x''<nowiki>''</nowiki><sub>0</sub> = ''x''<sub>1</sub>, ''x''<nowiki>''</nowiki><sub>1</sub> = ''x''<sub>3</sub>, ..., ''x''<nowiki>''</nowiki><sub>''n''<nowiki>'</nowiki>-1</sub> = ''x''<sub>''n''-1</sub> by ''f''<sub>0</sub><nowiki>''</nowiki>, ..., ''f'' <nowiki>''</nowiki><sub>''n''<nowiki>'</nowiki>-1</sub>. Then it follows:
