# How is the complexity of applying Short term fourier transform over n samples with a moving window of size m amount to O(nmlogm)

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.
• 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$. – robert bristow-johnson Feb 21 '14 at 4:14