Wir verwenden die Big-Θ Notation, um asymptotisch das Wachstum der Laufzeit einer Funktion nach oben und unten zu begrenzen. Manchmal wollen wir aber nur die obere Schranke betrachten. Zum Beispiel, obwohl die Worst-Case-Laufzeit der binären Suche Θ(lgn) \Theta (\lg n) ist, wäre es falsch zu sagen, dass die binäre Suche in jedem Fall Θ(lgn) \Theta (\lg n) Zeit in Anspruch nimmt. Was passiert, wenn wir den Zielwert bei der ersten Vermutung finden? Dann läuft der Algorihtmus in Θ(1) \Theta (1) Zeit. Die Laufzeit der binären Suche ist niemals schlechter als Θ(lgn) \Theta (\lg n) , aber sie ist manchmal besser. Es wäre praktisch, eine Form von asymptotischer Notation zu haben, die angibt, dass "die Laufzeit höchstens so stark wächst, aber sie könnte auch langsamer wachsen." Wir verwenden die "Big-O" Notation für solche Zwecke.
Wenn eine Laufzeit O, left parenthesis, left parenthesis, n, right parenthesis, right parenthesis ist, dann ist für große n die Laufzeit höchstens k, dot, f, left parenthesis, n, right parenthesis für die Konstante k. Man kann sich eine O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis Laufzeit so vorstellen:
6n^2 vs 100n+300
Wir sagen, dass die Laufzeit "Big-O von f, left parenthesis, n, right parenthesis", oder nur "O von f, left parenthesis, n, right parenthesis" ist. Wir verwenden die Big-O-Notation für asymptotische Obergrenzen , da sie das Wachstum der Laufzeit nach oben für hinreichend große Eingangsgrößen begrenzt.
Wir können nun die Laufzeit der Binärsuche in allen Fällen charakterisieren. Die Laufzeit der Binärsuche ist immer O(lgn) O(\lg n) ist. Wir können eine genauere Aussage über die Worst-Case-Laufzeit treffen: Sie ist Θ(lgn) \Theta (\lg n) . Aber die beste Aussage, die alle Fälle abdeckt ist, dass die binäre Suche in O(lgn) O (\lg n) Zeit läuft.
Wenn wir uns nochmal die Definition der Big-Θ Notation anschauen, stellen wir fest, dass sie der Big-O Notation stark ähnelt, mit dem Unterschied dass die Big-Θ Notation die Laufzeit von oben und unten, anstatt nur von oben, begrenzt. Wenn wir sagen, dass eine Laufzeit in einer bestimmten Situation Θ(f(n)) \Theta (f (n)) ist, dann ist sie auch O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Zum Beispiel können wir sagen, dass, weil die Worst-Case-Laufzeit der binären Suche Θ(lgn) \Theta (\lg n) ist, sie deswegen auch O(lgn) O (\lg n) ist. Der Umkehrschluß ist jedoch nicht unbedingt wahr: Wie wir gesehen haben, läuft die binäre Suche immer in O(lgn) O (\lg n) Zeit, aber nicht immer in Θ(lgn) \Theta (\lg n) .
Da die Big-O Notation nur eine asymptotische Obergrenze angibt und nicht eine asymptotisch enge Bindung, können wir Aussagen treffen, die auf den ersten Blick falsch erscheinen, aber trotzdem technisch korrekt sind. Zum Beispiel ist es absolut richtig zu sagen, dass die Binärsuche in O, left parenthesis, n, right parenthesis Zeit läuft. Das ist richtig, weil die Laufzeit nicht schneller als eine konstante Zeit n wächst. Tatsächlich wächst sie jedoch langsamer. Nehmen wir ein Beispiel. Angenommen, du hast 10 Euro in der Tasche. Du gehst zu deinem Freund und sagst: "Ich habe eine Menge Geld in meiner Tasche, und ich garantiere, dass es nicht mehr als eine Million Euro sind." Deine Aussage ist absolut wahr, wenn auch nicht schrecklich präzise. Eine Million Euro ist eine Obergrenze auf 10 Euro, genau wie O, left parenthesis, n, right parenthesis eine Obergrenze für die Laufzeit der Binärsuche ist. Andere, ungenaue, obere Schranken der Binärsuche wären O, left parenthesis, n, start superscript, 2, end superscript, right parenthesis, O, left parenthesis, n, start superscript, 3, end superscript, right parenthesis und O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Aber weder Θ(n) \Theta (n) , Θ(n2) \Theta (n ^ 2) , Θ(n3) \Theta (n ^ 3) und Θ(2n) \Theta (2 ^ n) wäre richtig um die Laufzeit der Binärsuche in jedem Fall zu beschreiben.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.