Betrachten wir eine einfache Implementation der linearen Suche:
var doLinearSearch = function(array) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // found it!
    }
  }
  return -1;  // didn't find it
};
Wir bezeichnen die Größe des Arrays (array.length) mit n. Die maximale Anzahl von Wiederholungen, die die for-Schleife ausführen kann, ist n, und der schlimmste Fall liegt vor, wenn der zu suchende Wert nicht im Array enthalten ist. Jedes Mal, wenn die for-Loop iteriert, muss sie mehrere Dinge tun: Vergleiche guess mit array.length; Vergleiche array[guess] mit targetValue, möglicherweise den Wert von guess zurückgeben, und guess inkrementieren. Jede dieser kleinen Berechnungen benötigt jedes mal, wenn sie ausgeführt wird, eine konstante Zeitspanne. Wenn die for-Schleife n mal iteriert, dann ist die Zeit für alle n Iterationen c, start subscript, 1, end subscript, dot, n, wobei c, start subscript, 1, end subscript die Summe der Zeiten für die Berechnungen in einer Schleifeniteration ist. Nun können wir hier nicht sagen, was der Wert von c, start subscript, 1, end subscript ist, denn es hängt von der Geschwindigkeit des Computers, der verwendeten Programmiersprache, dem Compiler oder Interpreter ab, der das Quellprogramm in den lauffähigen Code umwandelt, und von anderen Faktoren. Dieser Code hat ein bisschen extra Overhead, für die Einrichtung der for-Loop (einschließlich der Initialisierung von guess auf 0) und möglicherweise der Rückgabe von -1 am Ende. Wir nennen die Zeit für diesen Overhead c, start subscript, 2, end subscript, was auch eine Konstante ist. Daher ist die Gesamtzeit für die lineare Suche im schlimmsten Fall c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript.
Wie wir bereits gesehen haben, sagen der konstante Faktor c, start subscript, 1, end subscript und der niederwertige Term c, start subscript, 2, end subscript nichts über sie Wachstumsrate der Laufzeit aus. Bedeutsam ist hingegen, dass die Worst-case Laufzeit der linearen Suche mit der Arraygröße n wächst. Die Notation, die wir für diese Laufzeit verwenden, ist Θ(n) \Theta (n) . Das ist der griechische Buchstabe "Theta", und wir sagen "big-Theta von n" oder einfach nur "Theta von n".
Wenn eine bestimmte Laufzeit Θ(n) \Theta (n) ist, dann bedeutet dies, dass wenn n groß genug wird, die Laufzeit mindestens k, start subscript, 1, end subscript, dot, n und höchstens k, start subscript, 2, end subscript, space, dot, n für die Konstanten k, start subscript, 1, end subscript und k, start subscript, 2, end subscript ist. Man kann sich Θ(n) \Theta (n) so vorstellen:
6n^2 vs 100n+300
Für kleine Werte von n ist uns gleichgültig, wie die Laufzeit im Vergleich zu k, start subscript, 1, end subscript, dot, n oder k, start subscript, 2, end subscript, dot, n ist. Aber sobald n groß genug ist - also auf oder rechts von der gestrichelten Linie - muss die Laufzeit zwischen k, start subscript, 1, end subscript, dot, n und k, start subscript, 2, end subscript, dot, n liegen. Solange die Konstanten k, start subscript, 1, end subscript und k, start subscript, 2, end subscript existieren, sagen wir, dass die Laufzeit Θ(n) \Theta (n) ist.
Wir sind übrigens nicht auf n in Big-Θ Notation beschränkt. Wir können jede Funktion verwenden, wie z. B. n, start superscript, 2, end superscript, nlgn n \lg n oder jede andere Funktion von n. Man kann siech eine Laufzeit von Θ(f(n)) \Theta (f (n)) für eine beliebige Funktion f, left parenthesis, n, right parenthesis so vorstellen:
6n^2 vs 100n+300
Sobald n groß genug ist, liegt die Laufzeit zwischen k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesis und k, start subscript, 2, end subscript, dot, f, left parenthesis, n, right parenthesis.
Ein weiterer Vorteil der Verwendung der Big-Θ-Notation ist, dass wir uns keine Sorgen machen müssen, welche Zeiteinheiten wir verwenden. Angenommen, wir berechnen, dass eine Laufzeit 6, n, start superscript, 2, end superscript, plus, 100, n, plus, 300 Mikrosekunden ist. Oder vielleicht sind es auch Millisekunden? Wenn du die Big-Θ Notation benutzt, nennst Du keine Zeiteinheit. In der Praxis suchen wir den bestimmenden Term und lassen also Konstanten und Terme geringerer Ordnung fallen. Du lässt also den Faktor 6 und die Terme 100, n, plus, 300 fallen, und gibst lediglich an, dass die Laufzeit Θ(n2) \Theta (n ^ 2) ist.
Wenn wir die Big-Θ Notation verwenden, sagen wir, dass wir ein asymptotisch enges Intervall der Laufzeit haben. "Asymptotisch", weil es nur für große Werte von n zutrifft ist. "Intervall", weil die Laufzeit nach oben und nach unten beschränkt ist.

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.