Why is time complexity O(n) instead of O(wn)?

Courses
,
1

For each item in the inputlist we run a nested while loop below
while ((!window.isEmpty()) && nums.get(i) >= nums.get(window.peekLast()))

which can iterate the size of window in worse case scenario for each item in the inputarray.

why then the complexity is stated as O(n)? is’nt it O(wn)? where w is the window size and n is the nums.size();

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in Java

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in Java

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in Java

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in Java

3

Hello @bee1,

Upon further review, we have determined that the complexity of the algorithm is actually O(n + w) rather than O(n) as we had initially stated. We have updated the text to explain why the complexity is O(n + w) and not O(n) or O(n * w). We hope this helps to clarify your question.

If you still have any confusion, please let us know.
Thank you!