I dare say what I am about to write is no great revelation and indeed I was probably taught this for ‘A’ level maths, but forgot it…
Anyway, I was reading about the Fast Fourier Transform (FFT), which, discovered in the 1960s, radically improved the speed of signal analysis. Older algorithms had been able to analyse signal samples in time, while the FFT manages it in time.
It does this by relying on the fact that one can combine two samples to get a sample in operations, ie.,
Hence we can get samples in doublings. But how many operations does that take?
For the above example () we can see it is and for the more general case we can see this is – times an infinite series.
For the overall complexity of the algorithm to be this series should add to 1. Does it?
Yes, it does, and here’s a proof…
We can rewrite our series as…
As we know we get so