Laufzeit O(n · log n)

Worum geht es?

Eine linearithmische Laufzeit O(n · log n) liegt zwischen O(n) und O(n²) und ist die theoretische Untergrenze für vergleichsbasierte Sortierverfahren. Sie tritt bei Divide-&-Conquer-Algorithmen mit linearer Kombination auf — Merge Sort, Heap Sort, durchschnittliches Quick Sort, FFT.

Für praktische Eingabegrößen liegt n · log₂(n) sehr nah an O(n): bei n = 10⁶ unterscheiden sich Linear und O(n log n) nur um den Faktor ≈ 20.

Die Formel

Ops = n · log₂(n)

Die Variablen

Minimal-Beispiel

n = 1024:

Ops = 1024 · log₂(1024)
    = 1024 · 10
    = 10 240

Praxis-Beispiele

Beispiel 1 — n = 10⁹ (eine Milliarde)

Ops = 10⁹ · log₂(10⁹)
    ≈ 10⁹ · 30
    = 3 · 10¹⁰

Beispiel 2 — Untergrenze für Vergleichssortieren

Jeder vergleichsbasierte Sortieralgorithmus benötigt mindestens ⌈log₂(n!)⌉ Vergleiche:

log₂(n!) ≈ n · log₂(n) − n · log₂(e)
         ≈ n · log₂(n) − 1,443 · n

→ asymptotisch n · log₂(n).

Beispiel 3 — Klassenvergleich für n = 10⁶

O(n)        =        1 000 000
O(n log n)  ≈       19 930 000
O(n²)       = 1 000 000 000 000

n log n ist nur ca. 20× teurer als n,
aber 50 000× billiger als n².