Theta-Notation - Average-Case-Laufzeit#
Mit der Θ-Notation (Theta-Notation) wird die Laufzeit asymptotisch enger Intervalle für Laufzeiten von Algorithmen angegeben.
- asymptotisch, da es nur für große Werte gilt (ab einem großen \(n_0\))
- enges Intervall, da die qualitativen Schranken nach oben und unten begrenzt sind
Ab \(n_0\) muss die Laufzeit des Algorithmus innerhalb der Bänder \(k_1\) und \(k_2\) liegen.
Dann gilt: \(k_1(n) < Θ(n) < k_2(n)\)