Big O Notation: What A-Level CS Actually Expects

Big O Notation taucht in jeder großen A-level Informatik-Spezifikation auf (AQA, OCR, Edexcel) und bringt viele Schüler durcheinander – nicht weil die Mathematik schwer ist, sondern weil sie es nie mit echtem Code verknüpft sehen. Das ist eine praktische Übersicht über das, was du wissen musst und wie du Prüfungsfragen dazu beantworten kannst, ohne herum zu reden.

Was Big O wirklich misst

Big O beschreibt, wie die Laufzeit (oder Speichernutzung) eines Algorithmus wächst, wenn die Eingabegröße, üblicherweise n genannt, größer wird. Es ist keine Zeitmessung in Sekunden. Es ist eine Methode, die Wachstumsrate zu beschreiben, damit du Algorithmen unabhängig von Hardware vergleichen kannst.

Wenn du O(n) schreibst, sagst du: Wenn ich die Eingabe verdoppele, verdoppelt sich die Arbeit ungefähr auch. O(n²) bedeutet, dass eine Verdoppelung der Eingabe die Arbeit ungefähr vervierfacht. Diese Beziehung ist das, was Prüfer von dir erwarten – nicht exakte Operationszählungen.

Die Komplexitäten, die du beherrschen musst

Für A-level sind das die, die immer wieder vorkommen:

• O(1) – konstante Zeit. Auf ein Array-Element nach Index zugreifen: arr[5]. Spielt keine Rolle, wie groß das Array ist.
• O(log n) – logarithmisch. Binäre Suche in einer sortierten Liste. Jeder Schritt halbiert den verbleibenden Suchraum.
• O(n) – linear. Eine einzelne Schleife durch eine Liste, wie eine lineare Suche, die jedes Element einmal prüft.
• O(n log n) – linearithmisch. Merge Sort und Quicksort (Durchschnittsfall) landen hier.
• O(n²) – quadratisch. Verschachtelte Schleifen über dieselben Daten, was genau das ist, was Bubble Sort, Insertion Sort und Selection Sort machen.
• O(2ⁿ) – exponentiell. Naiver rekursiver Fibonacci ohne Memoisation. Wird schnell hässlich.

Du solltest in der Lage sein, Pseudocode anzuschauen und auf Anhieb zu sagen, welche dieser Kategorien es ist, weil das größtenteils das ist, was geprüft wird.

Code lesen und Komplexität bestimmen

Die Methode, die immer funktioniert: Zähle die Schleifen und sehe, wie sie sich zu n verhalten.

# O(n) - eine Schleife, ein Durchgang
for i in range(n):
    print(i)

# O(n^2) - verschachtelte Schleife, beide an n gebunden
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - der Suchraum halbiert sich bei jeder Iteration
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Eine verschachtelte Schleife, bei der die Range der inneren Schleife von n abhängt, ist immer noch O(n²), selbst wenn sie ein wenig anders aussieht (wie for j in range(i) statt for j in range(n) – das ist immer noch quadratisch insgesamt, nur mit einem konstanten Faktoren-Unterschied).

Pass auf bei Schleifen, die überhaupt nicht von n abhängen. Eine Schleife, die unabhängig von der Eingabegröße immer 10 Mal läuft, ist O(1), selbst wenn eine Schleife vorhanden ist. Prüfer mögen das gerne verstecken.

Häufige Sortieralgorithmen und deren Big O

Das ist ein beliebtes Prüfungsthema, weil es zwei Spezifikationen auf einmal verbindet: Sortieralgorithmen und Komplexität.

Algorithmus	Bester Fall	Schlechtester Fall
Bubble Sort	O(n)	O(n²)
Insertion Sort	O(n)	O(n²)
Merge Sort	O(n log n)	O(n log n)
Binäre Suche	O(1)	O(log n)
Lineare Suche	O(1)	O(n)

Merge Sorts Konsistenz (gleiche Komplexität im besten und schlechtesten Fall) ist erwähnenswert, wenn eine Frage fragt, warum du es für große Datenmengen wählen würdest statt Bubble Sort. Bubble Sorts bester Fall O(n) gilt nur mit einer Early-Exit-Optimierung, wenn keine Swaps in einem Durchgang stattfinden – erwähne dieses Detail, falls du es ansprichst, da einige Prüfungsorganisationen das erwarten.

Wo Schüler Punkte verlieren

Das Größte: