złożoność algorytmu sortowania

1 procedure proste wybieranie;
2 begin
3 for i := 1 to n − 1 do
4 k := i; x := A[i]; {k — indeks minimalnego elementu w A[i..n], x — element minimalny}
5 for j := i + 1 to n do
6 if A[j] < x then {czy bieżący element jest mniejszy niż dotychczasowe minimum}
7 k := j; x := A[j]; {aktualizacja minimalnego elementu}
8 end if;
9 end for;
10 A[k] := A[i]; A[i] := x; {zamiana elementu A[i] ze znalezionym minimalnym}
11 end for;
12 end.

(http://sun.aei.polsl.pl/~sdeor/students/aa/sort_wybieranie.pdf)
Obliczyłem jego złożoność T(n) = (n-i)(n-1) , jako operację dominującą przyjąłem porównanie. Niestety nie wiem jak pozbyć się "i" w wyniku. Ktoś wie jak to policzyć do końca?

rozwiązanie

w pewnym przybliżeniu: pozbywasz się wszystkiego poza n, wychodzi n^2.
w dobrym przybliżeniu: widzisz, że wewnętrzna pętla średnio wykonuje się n/2 razy w pętli wykonującej się n razy, więc masz n*n/2.
dokładnie: n dla zewnętrznej pętli trwa tak naprawdę (n-1) razy, więc (n-1)*n/2, czyli w notacji używanej przez wolfram: (n^2 - n)/2.