CODEWITHSUNDEEP
javaalgorithmloopstime-complexitynested-loops
susheelbhargavk
susheelbhargavk

Reputation: 97

How can there be two nested loops in this function and still have O(n) complexity?

Here is the solution to the problem of finding the minimum size of a subarray which has a sum greater than or equal to given number S:

public static int findMinSubArray(int S, int[] arr) {
    int windowSum = 0, minLength = Integer.MAX_VALUE;
    int windowStart = 0;
    for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        windowSum += arr[windowEnd]; // add the next element
        // shrink the window as small as possible until the 'windowSum' is smaller than 'S'
        while (windowSum >= S) {
            minLength = Math.min(minLength, windowEnd - windowStart + 1);
            windowSum -= arr[windowStart]; // subtract the element going out
            windowStart++; // slide the window ahead
        }
    }

    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

How is this O(n) but not O(n^2) or O(windowLength*n)?

Upvotes: 0

Views: 75

Answers (1)

ggorlen
ggorlen

Reputation: 56925

You'll never visit an element more than twice, once when it gets pushed onto the window and again when it leaves the window. That's two passes over arr; O(2n) == O(n).

Nested loops don't mean complexity is automatically quadratic. You have to look at the bound on the work being done. In this case, the inner loop only makes at most n total steps forward, not n steps for every element as is the case with a traditional doubly nested for loop arrangement.

Upvotes: 2

Related Questions