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 109 and 109 + 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 – n2. 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 – n2 = n2 – n2 = 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 n2 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.
CLICK HERE to find out more related problems solutions.