Time Complexity of this nested for-loop algorithm?

Question

I'm having some trouble calculating the bigO of this algorithm:

public void foo(int[] arr){
  int count = 0;
  for(int i = 0; i < arr.length; i++){
    for(int j = i; j > 0; j--){
      count++;
    }
  }
}

I know the first for loop is O(n) time but I can't figure out what nested loop is. I was thinking O(logn) but I do not have solid reasoning. I'm sure I'm missing out on something pretty easy but some help would be nice.

Ash · Accepted Answer · 2019-12-12 12:12:47Z

3

Let's note n the length of the array.

If you consider the second loop alone, it is just a function f(i), and since it will iterate on all elements from i to 1, its complexity will be O(i). Since you know that j<n, you can say that it is O(n). However, there is no logarithm involved, since in the worst case, i.e. j=n, you will perfrom n iterations.

As for evaluating the complexity of both loops, observe that for each value of i, the second loop goes throught i iterations, so the total number of iterations is

1+2+...+(n-1)= n*(n-1)/2=(1/2)*(n^2-n)

which is O(n^2).

answered Dec 12, 2019 at 12:12

Ash

4,7786 gold badges30 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Anatolii · Accepted Answer · 2019-12-13 18:23:53Z

2

If we consider c as a number of times count is incremented in the inner loop then the total number of times count is incremented can be represented by the formula below:

As you can see, the total time complexity of the algorithm is O(n^2).

edited Dec 13, 2019 at 18:23

answered Dec 13, 2019 at 18:18

Anatolii

14.8k5 gold badges38 silver badges70 bronze badges

Collectives™ on Stack Overflow

Time Complexity of this nested for-loop algorithm?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related