Complexity of Bubble Sort

Question

I have seen at lot of places, the complexity for bubble sort is O(n²).

But how can that be so because the inner loop should always runs n-i times.

for (int i = 0; i < toSort.length -1; i++) {
            for (int j = 0; j < toSort.length - 1 - i; j++) {
                if(toSort[j] > toSort[j+1]){
                    int swap = toSort[j+1];
                    toSort[j + 1] = toSort[j];
                    toSort[j] = swap;
                }
            }
        }

Answer 1

And what is the "average" value of n-i ? n/2

So it runs in O(n*n/2) which is considered as O(n²)

Answer 2

There are different types of time complexity - you are using big O notation so that means all cases of this function will be at least this time complexity.

As it approaches infinity this can be basically n^2 time complexity worst case scenario. Time complexity is not an exact art but more of a ballpark for what sort of speed you can expect for this class of algorithm and hence you are trying to be too exact.

For example the theoretical time complexity might very well be n^2 even though it should in theory be n*n-1 because of whatever unforeseen processing overhead might be performed.