## Sliding window statistics calculation complexity

### May 11, 2011

The following C++ code takes a sequence of *n* elements, *a _{1}, a_{2}, …, a_{n}*, and outputs a sequence of

*n – k + 1*elements. The

*i*-th output element is a maximal element in the subsequence

*a*. The runtime complexity of the code is

_{i}, a_{i + 1}, …, a_{i + k – 1}*O(n)*.

template <typename T> void insert(std::list< std::pair<T,unsigned int> > &l, T v) { unsigned int sp = 0; while (!l.empty() && l.back().first < v) { sp++; l.pop_back(); } l.push_back(std::pair<T,unsigned int>(v,sp)); } template <typename T> void advance(std::list< std::pair<T,unsigned int> > &l) { if (l.front().second > 0) l.front().second--; else l.pop_front(); } template <typename T> void max_in_window(T const *in, T *out, size_t n, size_t k) { std::list< std::pair<T,unsigned int> > l; unsigned int i; for (i = 0; i < k - 1 && i < n; i++) insert(l,in[i]); for (; i < n; i++) { insert(l,in[i]); out[0] = l.front().first; out++; advance(l); } }

Interestingly, an algorithm for the median in a sliding window will have runtime of at least *O(n log k)*, since such an algorithm can be used to sort *O(n / k)* sequences of length *O(k)* each:

Let *a _{1}, a_{2}, …, a_{n}* be a sequence of numbers in a known interval, say

*(0, 1)*. Create a sequence of length

*3n – 2*by padding the sequence with a prefix of

*(n – 1)*

*0*‘s and a suffix of

*(n – 1)*

*1*‘s. Now execute the sliding window median algorithm with the padded sequence as input, and with

*k = 2n – 1*.

The *i*-th output element will be the median of a sequence that is made of the entire sequence *a _{1}, a_{2}, …, a_{n}*,

*n – i*zeros, and

*i – 1*ones. That median is

*a*, the

_{(i)}*i*-th smallest elements of the sequence

*a*. Thus, the output of the algorithm will be the sorted sequence

_{1}, a_{2}, …, a_{n}*a*.

_{(1)}, a_{(2)}, …, a_{(n)}