What's the complexity of this simple algorithm?

Правка en1, от 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

Теги #complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский tiagonapoli 2020-11-22 07:34:43 723 Initial revision (published)