Laufzeit quadratisch O(n²)

Worum geht es?

Eine quadratische Laufzeit O(n²) entsteht typischerweise durch zwei ineinander verschachtelte Schleifen über dieselbe Eingabe. Klassische Beispiele: Bubble Sort, Selection Sort, Insertion Sort im Worst Case oder die naive Suche nach Duplikaten.

Quadratische Algorithmen werden ab n ≈ 10⁴ schnell unbenutzbar — eine Million Eingaben bedeuten bereits 10¹² Operationen.

Die Formel

Ops = n²

Umstellung:
    n = √Ops

Die Variablen

Minimal-Beispiel

Wie viele Operationen für n = 1000?

Ops = 1000²
    = 1 000 000 Ops

Praxis-Beispiele

Beispiel 1 — Vergleich zu O(n log n)

Sortieren von n = 10⁶ Einträgen — quadratisch vs. linearithmisch:

O(n²)       = 10¹²        Ops
O(n log n)  ≈ 2 · 10⁷     Ops

Faktor: 50 000-fach langsamer.

Beispiel 2 — Maximal mögliches n

Ein Algorithmus hat 10⁸ Ops Budget — wie groß darf n bei quadratischer Laufzeit werden?

n = √10⁸
  = 10 000 Elemente

Beispiel 3 — Verdopplung der Eingabe

Was passiert bei n: 1000 → 2000?

1000² =     1 000 000
2000² =     4 000 000

Vervierfachung der Operationen.