What's the complexity of this simple algorithm?

Revision en1, by tiagonapoli, 2020-11-22 07:34:43

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

Tags #complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English tiagonapoli 2020-11-22 07:34:43 723 Initial revision (published)