Pruned fast Fourier transforms compute only a specified subset of the result indices in faster time, although sometimes with a slower implementation constant (because FFT is generally so optimized). They can also exploit sparsity in the input vector to further accelerate computation. On http://www.fftw.org/pruned.html, the runtime is reported to be $\in O(n\log k)$, where $n$ is the length of the input vector and $k$ is the number of desired indices to compute in the result (of course, the standard FFT could always be used to compute the full result in $O(n\log n)$ steps); however, I cannot figure out where the benefit of sparsity in the input vector is measured in this bound.Does anyone know the runtime / how to get the runtime of a pruned FFT on $n$ inputs, $m$ of which are nonzero, and where $k$ outputs are computed? I have an algorithm that depends on a step very similar to a pruned FFT calculation, and I have a lot of sparsity.Thanks a lot for any advice you can lend.
Pruned FFT runtime
algorithm analysis;runtime analysis;fourier transform