Sliding Window Algorithm

Question

I know that the time complexity of the sliding window algorithm is o(N) but what is the time complexity of a variable-sized sliding window algorithm.

For eg-

array = [1,2,3,4,5,6]

when size of sliding window is = 1 window - [1], [2], [3], [4], [5], [6]

when size of sliding window is = 2 window - [1,2], [2,3], [3,4], [4,5], [5,6]

when size of sliding window is = 3 window - [1,2,3], [2,3,4], [3,4,5], [4,5,6]

and so on ...

window size will range from 1 to n (valid values for window size). If creating a single-window costs O(N) then creating N windows will cost O(N^2)?

Answer 1

Running a sliding window across an array is O(n) regardless of the size of the window.

The head pointer and tail pointers increase monotonically for all window sizes. In contrast, a typical nested loop quadratic algorithm runs the inner index j from i to n for every outer index i.

The assumption here is that you're not doing any extra work besides the deque offers and polls (which are constant time for each i) such as looping over the window for every i.

If you're creating n windows from 1 to n, you're back to the classical nested-loop quadratic algorithm, O(n^2).