educative.io

Educative

Why is the Time Complexity O(N) for smallest sub array?

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) .

1 Like

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.

4 Likes

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?

2 Likes

“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”.

4 Likes

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:

  • a). the arr is [1, 2, 3, 4, 5] the s is 100;
  • b). the 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? :slight_smile:

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 :slight_smile:

Cheers

3 Likes