Calculating algorithmic complexity for median smoothing in Time Series

Question

If my question is not for this forum, please tell and i'll delete it. This question more theoretically. A time series with T observations is given. Median smoothing with width window of n was applied to this series. How can i calculate algorithmic complexity for the most efficient algorithm for this median smoothing, depending on T and n?

Answer 1

The median of $N$ elements can be obtained in linear time $O(N)$ by the median-of-medians method. So applied to every window, you achieve the complexity $O((T-N)N)$, which can be $O(TN)$.

But you can also keep the elements in a balanced binary search tree which you update incrementally. This yields a complexity $O(N\log N+(T-N)\log N)$ which can be $O(T\log N)$.

But these are just upper bounds.