PPT-Folie
Cmin(N) = N-1 Cmax(N) = S i=2..N i = Q(N2) Mmin(N) = 2(N-1) Mmax(N) = S i=2..N i+1 = Q(N2)
Für die Abschätzung der Werte C mit und M mit kann man davon ausgehen, daß im Mittel die Hälfte der maximalen Vergleiche/Bewegungen ausgeführt werden müssen.
Auch hier erhält man also Q(N2).