## Issue

for loop inside subArraySum calls sumArray which also contains a for loop. Would this be considered O(n^2) time? Go easy on me as this is my first ever question and as you can see from my code, I’m a beginner. This is my code:

```
const subArraySum = (arr,n) => {
let i = 0;
let result = [];
for (let j = n-1;j<arr.length;j++) {
let li = arr.slice(i,j+1);
result.push(sumArray(li));
i++;
}
return maxResult(result);
}
function sumArray(li) {
counter = 0;
for (let k of li) {
counter+=k;
}
return counter;
}
function maxResult(result) {
let highest = 0;
for (let k of result) {
if (k>highest) {
highest = k;
}
}
return highest;
}
```

## Solution

While `for`

and other looping constructs may provide some basic guides on complexity, the analysis must always consider the number of iterations and not rely on counting the number of nested loops. It can be easily shown that any number of nested loops can still result in linear or constant time complexity (i. e. `while (true) { break; }`

).

For the functions you mentioned, both `sumArray`

and `maxResult`

run `n`

iterations, where `n`

matches the count of input array elements.

For `subArraySum`

, however, the complexity is not as trivial. We can easily see, that the function calls both `sumArray`

and `maxResult`

, however, it is not exactly clear how these invocations relate to the function inputs.

To invoke `subArraySum`

for some array `arr`

of length `m`

and an argument of `n`

, we can see that the `for`

loop runs from `n - 1`

to `m`

, that is `m - n + 1`

times, or in complexity terms, the loop run count is a function of `O(m - n + 1)`

= `O(m - n)`

. The constant 1 is considered insignificant for the purpose of asymptotic analysis (imagine the difference between 10^{9} and 10^{9} + 1 operations – probably not that much).

Each loop then makes a sub-array of length `n - 1`

. This is based on the `i`

and `j`

iteration variables – I may be wrong here but I suspect the implementation is. Regardless, that makes an `O(n)`

operation.

The slice is then summed via `sumArray`

(complexity of `O(n)`

as described previously) and inserted to the back of another array (amortized `O(1)`

).

Therefore, each run of the loop has complexity of `O(n)`

.

As the loop runs `O(m - n)`

times and has a complexity of `O(n)`

, yielding a total complexity of `O(n * (m - n))`

= `O(m * n - n^2)`

.

Let’s now consider this term, *m* * *n* – *n*^{2}. From the semantics of the function, we can assume, that it must always hold that *n* < *m* (the complexity is constant for *n* = *m*: *m* * *n* – *n*^{2} = *n*^{2} – *n*^{2} = 0 – you can confirm this by mentally going through the algorithm, it would just return 0 without any looping). If *n* is always smaller than *m*, then *n*^{2} will always be smaller than *m* * *n* and therefore can be ignored.

We arrive at `O(mn)`

for the loop.

At the end, `maxResult`

is invoked for the array of sums which is `O(m - n)`

long (remember that we created the array by running `O(m - n)`

iterations, each adding a single number to the array). This gives us `O(m - n)`

complexity for the `maxResult`

call.

With complexity `O(mn)`

+ `O(m - n)`

, we can, again apply the *n* < *m* and see that the second term always yields smaller value than the first one and therefore can be considered insignificant for the analysis.

So we arrive at the result, the algorithm has a time complexity of `O(mn)`

where `m`

is the length of the input array and `n`

is the length of the sub-arrays.

Answered By – Zdeněk Jelínek

Answer Checked By – Willingham (BugsFixing Volunteer)