tiagonapoli's blog

What's the complexity of this simple algorithm?
By tiagonapoli, history, 4 years ago, In English

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

Spoiler
  • Vote: I like it
  • +26
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply