I have been trying to understand a publication here where Short time fourier transform is applied over n samples in steps of m samples each (m is the size of the moving window). I understand that the computational complexity of the Short time fourier transform for m samples is mlogm.

The operation also consists of extracting energy from the samples. Since there are m samples in the window, I believe it should be O(m) in the worst case. So , as per my understanding, the complexity of the whole operation should be O(n/m * (mlogm + m)) = O(nm). Since there n/m windows and each window has mlogm for fourier transform and m for signal strength extraction.

But the publication shows the complexity as O(nmlogm). Please help me understanding this.


evidently the author is performing an FFT $n$ times (or, if the window hop is not 1 sample, it would be proportional to $n$) and each FFT costs something proportional to $m \log(m)$). all this is quite normal.

| improve this answer | |
  • $\begingroup$ Thanks,.. but wouldn't the number of window hops be just n/m given that the window size is m? Also, if in the worst case , m is 1 and FFT could be done n times.. that would lead to nmlogm but m = 1 would make it zero.. $\endgroup$ – quirkystack Feb 21 '14 at 3:36
  • $\begingroup$ no. the windows (or "frames") can overlap. the degree of overlap is a parameter that someone sets for a particular purpose. a 50% overlapping window would have a hop of $\frac{m}{2}$. given a hop displacement of $k$ samples, the percent overlap would be $\frac{m-k}{m} \times$ 100%. or you can derive the window hop displacement given the percent overlap. but even if the hop displacement is a function of the window length $m$ or not, the number of windows (or frames) is $\mathrm{ceil}\left(\frac{n}{k}\right)$ which is virtually proportional to $n$. $\endgroup$ – robert bristow-johnson Feb 21 '14 at 4:14

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.