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
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.