How to calculate the complexity of this simple loop?
// v is an array with n elements, n <= 10^5
for(int i=0;i<n;i++) {
int sum = 0;
for (int j = i + 1;j < n && sum < v[i]; j++) {
sum += v[j];
// O(1) block
}
}
It seems the worst case scenario would be something like:
In which case the number of operations would be $$$O(nlog(maxElement))$$$, but I'm not being able to prove the complexity.
Background: a similar algorithm is used in the following problem and I wasn't able to understand the solution's complexity analysis