I know the efficiency for an $N$ point 2-radix FFT is $N\log_2(N)$ but assuming $k\leq N$, what if you were looking for the efficiency of calculating $k$ positions of the FFT? Would the efficiency be $k\log_2(N)$?



The FFT is pretty much an "all or nothing" algorithm. There is almost no efficiency gain in reducing the number of desired outputs.

For $k \ll N$ the Goertzel algorithm is typically the better choice. See https://en.wikipedia.org/wiki/Goertzel_algorithm. The break even point is quite small. Maybe $k = 4\cdot log_2(N)$ or thereabouts.

  • $\begingroup$ Thank you! I think that was the algorithm I was looking for. $\endgroup$ – digger1235 Mar 19 '18 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.