Time complexity of while loop inside for loop

user_14373820 0
Viewed 571

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.

time-complexity java
1 Answers

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

No, it isn't.

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 total complexity is O(n).

Q.E.D.

user_46077330
Related