Bubblesort  Zeitkomplexität am Beispiel eines Feldes mit 8 Elementen


12	34	65	23	17	33	20	8	

12	34	23	17	33	20  	8	65	größtes Element hinten

12	23	17	33	20  	8	34	65	zweitgrößtes Element an entsprechender Stelle

12	17	23	20  	8	33	34	65	drittgrößtes Element an entsprechender Stelle

12	17	20  	8	23	33	34	65

12	17	8	20  	23	33	34	65

12	8	17	20  	23	33	34	65

8	12	17	20  	23	33	34	65	kleinste Element ist vorn -> fertig


In jeder Zeile werden alle 8 Elemente "angefasst".
Wenn es doppelt so viele Elemente gibt, dann werden auch doppelt so viele Elemente "angefasst"  (~ n).
Es gibt n Zeilen. Wenn es doppelt so viele Elemente gibt, dann gibt es auch doppelt so viele Durchläufe  (~ n). 

Zusammengefasst:  t ~ n^2