A simple interpretation requires operations. The FFT requires if N is a factor of two. In general, FFT style techniques can be used for any N - firstly N is decomposed into prime factors and then a recursive ``butterfly'' operation is performed for each factor.
The ``Decimation in Time'' algorithm (Cooley and Turkey, 1965):
Start with the top level Fourier transform described by:
Now write as a summation of odd terms and even terms:
That is, the original Fourier transform has been written in terms of two Fourier transforms operating on the odd and even portions of the data.
This recursion can be continued until the trivial case of one point is reached.