In this post I learned n point FFT is fft(x[1:N]).
Why it is not fft(x)[1:N]?
If it is fft(x[1:N]), does it make the complexity to be O(1)? Instead of depending on signal length?
Asked
Active
Viewed 115 times
0
hxd1011
- 885
- 2
- 11
- 23
1 Answers
3
An N-point FFT has complexity O(N log N). Indeed independent of original signal length.
fft(x)[1:N] does not yield the same values as fft(x[1:N]). They each represent a different set of frequencies.
Cris Luengo
- 55,762
- 10
- 62
- 120
-
In many cases, we just return fixed say length 4096 results for any inputs then it is actually O(1) respect inputs? – hxd1011 May 09 '20 at 16:00
-
@hxd1011: Yes. O(1) means that the computation time is fixed no matter how large the input is. That is the case here. It doesn’t mean it’s cheap or fast, it just means independent of input size. – Cris Luengo May 09 '20 at 16:41
-
@CrisLuengo Can I interest you in a [bounty for a 2D FFT question](https://stackoverflow.com/q/61718126/176769)? – karlphillip May 17 '20 at 23:04