What are some of the differences between DFT and FFT that make FFT so fast? I'm&nbsp;trying to understand FFTs, here's what I have so far:

In order to find the magnitude of frequencies in a waveform, one must probe for them by multiplying the wave by the frequency they are searching for, in two different phases (sin and cos) and averaging each.  The phase is found by its relation to the two, and the code for that is something like this:

//simple pseudocode
var wave = [...];                //an array of floats representing amplitude of wave
var numSamples = wave.length;
var spectrum = [1,2,3,4,5,6...]  //all frequencies being tested for.  

function getMagnitudesOfSpectrum() {
   var magnitudesOut = [];
   var phasesOut = [];

   for(freq in spectrum) {
       var magnitudeSin = 0;
       var magnitudeCos = 0;

       for(sample in numSamples) {
          magnitudeSin += amplitudeSinAt(sample, freq) * wave[sample];
          magnitudeCos += amplitudeCosAt(sample, freq) * wave[sample];
       }

       magnitudesOut[freq] = (magnitudeSin + magnitudeCos)/numSamples;
       phasesOut[freq] = //based off magnitudeSin and magnitudeCos
   }

   return magnitudesOut and phasesOut;
}


In order to do this for very many frequencies very quickly, FFTs use many tricks.

What are some of the tricks used to make FFTs so much faster than DFT?

P.S. I have tried looking at completed FFT algorithms on the web, but all the tricks tend to be condensed into one beautiful piece of code without much explanation.  What I need first, before I can understand the entire thing, is some introduction to each of these efficient changes as concepts.

Thank you.
The naive implementation of an $N$-point DFT is basically a multiplication by a $N \times N$ matrix. This results in a complexity of $\mathcal{O}(N^2)$.

One of the most common Fast Fourier Transform (FFT) algorithm is the radix-2 Cooley-Tukey Decimation-in-Time FFT algorithm. This is a basic divide and conquer approach. 

First define the "twiddle factor" as:
$$W_N \triangleq e^{-j\frac{2\pi}{N}}$$
where $j \triangleq \sqrt{-1}$ is the imaginary unit, then the DFT $X[k]$ of $x[n]$ is given by
$$X[k] = \sum_{n=0}^{N-1} x[n] \, W_N^{kn} \, .$$
If $N$ is even (and $\tfrac{N}{2}$ is an integer), the sum can then be divided in two sums as follows
$$X[k] = \sum_{n=0}^{N/2-1} x[2n]W_N^{2kn} + \sum_{n=0}^{N/2-1} x[2n+1]W_N^{k(2n+1)}$$
where the first summation deals with the even samples of $x[n]$ and the second with the odd samples of $x[n]$. Defining $x_e[n] \triangleq x[2n]$ and $x_o[n] \triangleq x[2n+1]$ and using the fact that


$W_N^{k(2n+1)} = W_N^{2kn}W_N^k$, and
$W_N^{2kn} = W_{N/2}^{kn}$,


this can be re-written as
$$
\begin{align}
X[k] &amp;= \sum_{n=0}^{N/2-1} x_e[n] W_{N/2}^{kn} + W_N^k\sum_{n=0}^{N/2-1} x_o[n]W_{N/2}^{kn} \\
&amp; = X_e[k] + W_N^k X_o[k]
\end{align}
$$
where $X_e[k]$ and $X_o[k]$ are the $\tfrac{N}{2}$-point DFT transforms of the even and odd samples of $x[n]$ respectively. So we just transformed a single $N$-point DFT into two smaller $\tfrac{N}{2}$-point DFTs.  This reduces computational cost because
$$ 2 \left( \frac{N}{2} \right)^2 + N &lt; N^2 $$
when $N &gt; 2$.

We can then re-iterate the same process on those two smaller DFTs. This divide-and-conquer approach allows to reach complexity of $\mathcal{O}(N\log N)$, which is way better than the $\mathcal{O}(N^2)$ we had with the naive DFT implementation (as is greatly illustrated by leftaroundabout's answer).