3 ms·
Little known fact: FFT is an O(nlgn) algorithm, but incremental FFT is O(n), meaning that if you want to compute FFT on the past n points of a stream of samples
by utopcell 4y ago
Little known fact: FFT is an O(nlgn) algorithm, but incremental FFT is O(n), meaning that if you want to compute FFT on the past n points of a stream of samples, it only takes O(n) to compute it for every new incoming sample.
- jononor 4y agoO(n) for every new samples is O(n*2) when seen over time/samples?
- artemisart 4y agoYes but you have no choice for streaming/real-time applications or anytime you need results for each sample, where doing the full recompute would be O(n^2 log n) total.
- fhars 4y agoNo, it is O(mn) if your stream is m samples long, compred to O(m n lg(n)) for the alternative.
- rencrisa 4y ago@utopcell do you have a reference for incremental FFT? I'm not sure if I understand what your implying. Given a polynomial f(X), obtaining f's evaluations over the n-th roots of unity takes O(nlogn) using FFT. Are you stating that obtaining g(X) != f(X) evaluations over the n-th roots of unity should take O(n) time assuming some precomputation derived in the FFT for f?
- utopcell 4y agoIf X_k is the coefficient for the sample window (x_0, x_1, .., x_{n-1}) and X'_k is the coefficient for window (x_1, .., x_n) then X'_k = (X_k + x_n - x_0)exp(2pik/n).