Summing an infinite series

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 $N$ signal samples in $O(N^2)$ time, while the FFT manages it in $O(Nlog_2N)$ time.

It does this by relying on the fact that one can combine two $N$ samples to get a $2N$ sample in $N$ operations, ie.,

$N \rightarrow 2N$ in $N$ operations
$2N \rightarrow 4N$ in $2N$ operations
$4N \rightarrow 8N$ in $4N$ operations

Hence we can get $N$ samples in $log_2N$ doublings. But how many operations does that take?

FFT of Mona Lisa. Public domain image

For the above example ( $N = 8$ ) we can see it is $\frac{N}{2} + \frac{N}{4} + \frac{N}{8}$ and for the more general case we can see this is $N(2^{-1} + 2^{-2} + ... )$ – $N$ times an infinite series.