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

**Spoiler**

Every time the sum at least doubles so it takes log(maxElement) times doubling to surpass maxElement.

This doesn't explain anything apart from where can $$$\log$$$ appear, does it? Maybe I don't understand something simple...

You're right, I didn't carefully look at the code to see "sum < v[i]" instead of "sum < v[j]".

Basically, for every element we build a segment to the right on which sum shouldn't exceed this element. Let's look at left borders of all the segments covering one particular element $$$a_{p}$$$: $$$l_{1} < l_{2} < \ldots < l_{k}$$$. For every $$$i$$$ $$$a_{l_{i}} \ge sum_{t = l_{i} + 1}^{p} a_{t}$$$ and this sum includes $$$a_{l_{j}}$$$ for all $$$j > i$$$. This means that $$$a_{l_{1}} \ge a_{l_{2}} \ge \ldots \ge a_{l_{k}}$$$. And this means that $$$a_{l_{i}} \ge a_{l_{i + 1}} + a_{l_{i + 2}} \ge 2 \cdot a_{l_{i+2}}$$$, so if we go back 2 left borders, the element will increase at least 2 times. That can't happen more than $$$\log C$$$ times, so the number of segments covering $$$a_{p}$$$ is bounded by $$$2 \log C$$$. Total length of all segments = sum over all $$$p$$$ number of segments covering $$$a_{p}$$$, so this is bounded by $$$2 n \log C$$$.