educative.io

Time complexity of sliding window problem challenge 3

Courses
,
#1

There is a while loop inside the for loop. Wondering why the time complexity is O(N+M) not O(N^2+M)?

1 Like
#2

I have the same question. Could someone help out here?

#3

Hi,

While loop only accesses each character 1 time while shrinking that’s why its time complexity is O(N).
For loop time complexity is also O(N) for the same reason.
So both loops complexity is O(N + N) = O (N)

O(M) is the time complexity for iterating over a pattern having M length.
That’s the reason for solution complexity being O(M + N).

Thanks