Minimal slip algorithm

Question

This is a home problem. Let A [] be an array of integers and the integer size of the K-window. Create an array of M minima visible in the window when it glides along A. I found an article with a solution for this problem, but I did not understand why O (n) is complicated. Can anyone explain this to me?

Answer 1

This is usually caught by people. You might think that it will take O(N^2)time, since you add, it takes time O(N), and you have the elements O(N). However, each element can be implemented only once and deleted once. Thus, a total of gliding over the entire array Ais required O(N).

This gives amortized efficiency O(1)every time you move a sliding window one element. In other words, the average time required to move the sliding window by one element is O(1).