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$$$.