We have a outer for loop and an inner while loop.
we are going to loop through inner while loop some x times (x<N) for every element of outer loop.
the how we come to conclusion that complexity is O(N) .
We have a outer for loop and an inner while loop.
we are going to loop through inner while loop some x times (x<N) for every element of outer loop.
the how we come to conclusion that complexity is O(N) .
The âwhileâ loop can iterate a maximum of ânâ times, as it is shrinking the sliding window (we canât have more than ânâ executions of windowStart++). This means the overall time complexity will be O(n+n); ânâ for the âforâ loop and an ânâ for the âwhileâ loop. This is asymptotically equivalent to o(n).
Hope we were able to clarify your question.
I am not sure that this is correct. How can an outer for loop that runs ânâ times and an inner while loop that runs âat most n timesâ have a time complexity of O(n+n)? I believe the complexity would need to be O(n*n) or O(n^2) because the while loop runs once for each iteration of the for loop. Am I missing something?
âthe while loop runs once for each iteration of the for loopâ
The âwhileâ loop doesnât run once for each iteration of the âforâ loop. It only runs for a total of ânâ times for all iterations of âforâ loop. This can also be seen from windowStart += 1; we canât have more than ânâ increments in âwindowStartâ.
Thank you!
@Design_Gurus Can you clarify further?
I understand that the while
loop doesnât run on every iteration of the for
loop: the while
loop will only loop if window_sum >= s
.
It seems to me, as @Justin_lin states above, that the while
loop can run up to window_length
times because it can keep shrinking the window until the window no longer has a sum of at least the target sum. Doesnât this imply a worst case run time of O(N^N) -> O(N^2)
?
Separately, but perhaps relatedly, I donât understand why this statement is true:
That is, how do we know the while
loops runs a total of N
times?
Thanks in advance!
The same doubt with you.
I also understand the while
loop doesnât run every iteration, and it depends on the condition window_sum >= s
. But I donât know how to evaluate the time complexity of this kind of problem.
So, I try to enumerate the bad cases, and here are the two boundary cases I suppose:
arr
is [1, 2, 3, 4, 5]
the s
is 100;arr
is [1, 2, 3, 4, 99]
the s
is 100;In the 1st case, the inner while
loop will get executed 0 times, and in the 2nd case, it will run N
times.
I donât know whether is or not the correct way to explain this.
I donât understand either, why it is has O(N) time complexity?
Is there a way we can do O(n log n) time?
Hi! Let me try to explain why it is O(N) with a couple of examples.
It is possible for the inner loop to run once FOR ALL the outer iterations, not once PER outer iteration. Example:
S=14 and array [1, 1, 1, 18]
array[0] = 1, windowSum 1 -> condition does NOT match
array[1] = 1, windowSum 2 -> condition does NOT match
array[2] = 1, windowSum 3 -> condition does NOT match
array[3] = 18, windowSum 21 -> condition matches, letâs try shrinking
-array[0] = -1, windowSum 20 -> condition still matches, letâs keep shrinking
-array[1] = -1, windowSum 19 -> condition still matches, letâs keep shrinking
-array[2] = -1, windowSum 18 -> condition still matches.
-array[3] = -18, windowSum 0 -> condition does not match anymore, inner loop ends. Outer loop ends.
In this scenario, outer loop iterates over each one of the elements, but inner loop only runs for the LAST element, and loops over the 4 elements. In other words, the loop runs only once for ALL iterations of the outer one, not once for each iteration.
Complexity is O(N + N) = O(N).
But is that the worst possible case? (which is likely the question we all have). Well, we could think that there is still the chance that inner loop executes for EVERY iteration of the outer one, which seems worse. But that is only possible if condition (windowSum >= S) matches for every outer iteration, so shrinking is needed for all of them. Letâs see how it performs in that case:
S = 2 and array [2, 2, 2]
array[0] = 2, windowSum 2 -> condition MATCHES, letâs shrink
-array[0] = -2, windowSum 0 -> condition does NOT match anymore, letâs grow
array[1] = 2, windowSum 2 -> condition MATCHES, letâs shrink
-array[1] = -2, windowSum 0 -> condition does NOT match anymore, letâs grow
array[2] = 2, windowSum 2 -> condition MATCHES, letâs shrink
-array[2] = -2, windowSum 0 -> condition does not match anymore. Inner loop ends. Outer loop ends.
In this case, inner loop (shrinking) executes for each element iterated by outer loop, but turns out it iterates exactly once over every element of the array for ALL outer iterations TOGETHER (not for EACH one). See how each element iterated by outer loop runs shrinking but the inner loop only visits a SINGLE element before the condition is violated.
Complexity is O(N + N) = O(N).
Another example:
S = 2 and array [3, 2, 1]
array[0] = 3, windowSum 3 -> condition MATCHES, letâs shrink
-array[0] = -3, windowSum 0 -> condition does NOT match anymore, letâs grow
array[1] = 2, windowSum 2 -> condition MATCHES, letâs shrink
-array[1] = -2, windowSum 0 -> condition does NOT match anymore, letâs grow
array[2] = 3, windowSum 3 -> condition MATCHES, letâs shrink
-array[2] = -3, windowSum 0 -> condition does NOT match anymore, inner loop ends, outer loop ends.
Once again, shrinking happens for each element, but inner loop only iterates over a single element per shrinking execution. (Which is the same case than the previous one).
Hope that makes it clear. It did for me
Cheers