Jak rozumiem, złożoność algorytmu to maksymalna liczba operacji wykonywanych podczas sortowania. Zatem złożoność sortowania Bubble powinna być sumą postępu arytmetycznego (od 1 do n-1), a nie n ^ 2. Następująca implementacja liczy liczbę porównań:

public int[] sort(int[] a) {
    int operationsCount = 0;
    for (int i = 0; i < a.length; i++) {
        for(int j = i + 1; j < a.length; j++) {
            operationsCount++;
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    System.out.println(operationsCount);
    return a;
}

Wyjście tablicy z 10 elementami wynosi 45, więc jest to suma progresji arytmetycznej od 1 do 9.

Dlaczego więc złożoność sortowania Bubble jest n ^ 2, a nie S (n-1)?