Analyse von for-Schleifen

Beispiel:

Minimumsuche in einem Array der Länge $n$

min = a[0];
for (i = 1; i < n; i++){
       if(a[i] < min) min = a[i];
}

Laufzeit $O(n)$ für	best case
	worst case
	average case.

Beispiele:

for (i = 0; i < k; i++) {             for (i = 0, i < k; i++) {
   for (j = 0; j < k; j++) {             for (j = 0; j < k; j++) {
      brett[i][j] = 0;                      if (a[i] == a[j]) treffer = true;
   }                                     }
}                                     }

$k^2$ Schritte für $k^2$ Daten	$\qquad \qquad \qquad \qquad$	$k^2$ Schritte für $k$ Daten
$\Rightarrow O(n)-$Algorithmus		$\Rightarrow O(n^2 )-$Algorithmus