What is the complexity of 2 loops with the inside loop starting at the first ones actual index?

Question

people of the internet,

I am studying algorithms and their complexity and I wrote a "naive" code for finding the number of inversions in an Array. First, it seemed easy and then I started wondering if that j=i+i changes the second loop's complexity from O(n) in a worst-case scenario to something lower ?

Here is my code written in java :

public static void naiveInversionCount(int[] T){
    int count = 0;
    for(int i = 0; i < T.length -1; i++){ // O(n)
        for(int j = i+1; j < T.length; j++){ // O(n) ???
            if(T[i]> T[j]) count++; // O(1)
        }
    }
    System.out.println("Naive method returns : " + count);
}

Thank you very much

Answer 1

The outer loop runs exactly n times.

The inner loop runs n−1, n−2, …, 0 times per outer loop. That is, on average, n/2 times.

And count++ runs exactly once per loop.

Thus the nested loop runs 1·n(n/2) times, which is in 𝑂(n²).