Also notice the awesome "Sparse FFT" https://groups.csail.mit.edu/netmit/sFFT/ https://groups.csail.mit.edu/netmit/sFFT/ which takes time just about `k log (n/k

Also notice the awesome "Sparse FFT" https://groups.csail.mit.edu/netmit/sFFT/ https://groups.csail.mit.edu/netmit/sFFT/ which takes time just about `k log (n/k)` to recover the `k` largest coefficients. So often a complete Fourier transform is taken only to immediately discard nearly all of the computed values. (Compression for example.)