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:

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

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