CODEWITHSUNDEEP
javatime-complexity
Tair Itzhak
Tair Itzhak

Reputation: 43

Time complexity of while loop inside for loop

I'm writing an algorithm that needs to find the length of smallest subarray that its sum is larger than given k parameter.

This is the function I wrote so far:

    public static int smallestSub (int [] a, int k) {
        int currSum = a[0];
        int start = 0;
        int minLen = a.length + 1;
        int currLen = 1;
        
        for (int i = 1; i < a.length; i++) {
            currSum += a[i];
            currLen++;

            while (currSum - a[start] > k && start < i) {
                currSum -= a[start];
                start++;
                currLen--;
            }

            if (currSum > k) {
                minLen = Math.min(currLen, minLen);
            }
        }

        return minLen;
    }

My question is: is the complexity of this algorithm O(n^2)? I'm asking since while loop depends on for loop.

Upvotes: 3

Views: 1703

Answers (1)

logi-kal
logi-kal

Reputation: 7880

is the complexity of this algorithm is O(n^2)?

TL;DR version: No, it isn't. It is in fact O(n).

Long version:

First, let us notice that i goes from 1 to n (I suppose a.length is what you call n).

The inner loop increments start until it reaches i, but it doesn't restart from 0. Therefore, for each iteration of the outer loop, you start from a certain start' and you reach a certain start'' (that is at most the current value of i). Notice that start' is equal to the start'' of the previous step.

Let us call delta_i the difference (start'' - start')_i, i.e. the number of iterations of the i-th inner loop.

The cost of the algorithm is the number of overall iterations of the inner loop. This can be computed as:

Σ_(i=1)^n {delta_i} = delta_1 + ... + delta_n
                    = (start'' - start')_1 + ... + (start'' - start')_n
                    = start''_1 - start'_1 + ... + start''_n - start')_n
                    = -start'_1 + start''_n

The last step is because every start'_i is equal to the next start'_(i+1) (for instance, start''_1 = start'_2), so they can be simplified. But start'_1 = 0, so we end up with just start''_n, which is at most n.

Thus, the overall complexity is O(n).

Upvotes: 3

Related Questions