### tiago.napoli's blog

By tiago.napoli, history, 10 days ago,

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:

$2^k, 2^{k-1}, 2^{k-2}, ..., 2^0, 2^0$

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

• +26

 » 10 days ago, # |   0 Every time the sum at least doubles so it takes log(maxElement) times doubling to surpass maxElement.
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 This doesn't explain anything apart from where can $\log$ appear, does it? Maybe I don't understand something simple...
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 You're right, I didn't carefully look at the code to see "sum < v[i]" instead of "sum < v[j]".
 » 10 days ago, # |   +12 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$.