[Peaker]

I thought normally k=n, and the ordinary complexity is O(n log(n)). So this sounds worse for the normal case.

I guess if you use a smaller k it is useful.

[thwest]

Most signals you get by sampling real world objects will be fairly sparse. You can expect anywhere between 50% and 95% of the coefficients in a wavelet or fourier domain to be near zero depending on the class of signal.

However, be wary of algorithms that expect K as input, as they are asking you to classify your signal before analysis.