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.

Answer 1

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

Answer 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:

enter image description here

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