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.