> with N if it's a power of 2.
with N if it's highly composite. See, e.g. http://www.fftw.org/ which works fairly well even for non-powers of 2.
Very interesting : I was actually thinking about redoing the spectrometer music visualization for MythTV to be use 'piano keyboard' pitches (rather than the FFT that they're using at the moment). And I came to the conclusion that some kind of recurrence (short) resonant filter would do the trick (with 88 different copies) - but never got further than that, since I had limited imagination about what algorithms to search for. Unfortunately, I've got overwhelmed with other projects now...
If you only want to detect one frequency, can't you jut use the "slow" fourier transform?
Yes, the discrete Fourier transform (DFT) detects N frequencies in parallel, where N is the block size, and you can disregard the uninteresting frequencies. The fast Fourier transform (FFT) is an efficient algorithm that computes the DFT. For detecting M frequencies where M << N, the Goertzel algorithm requires less computation than the FFT. Also, the Goertzel algorithm allows targeting more exact frequencies regardless of the sampling rate (Fs), while the FFT's bins have a fixed spacing of ±Fs/N.
As with everything, there are trade-offs associated with these three options.
But for larger M, it's better to do the FFT, since that gives you back O(N) frequencies in O(NlogN) time - because of the tricks it can do with N if it's a power of 2.