EMZETT.Kurz erklärt
Die Big-O-Notation beschreibt, wie stark der Zeit- oder Speicherbedarf eines Algorithmus mit der Eingabegröße n wächst – ohne Rücksicht auf Konstanten und konkrete Hardware.
Genauer
Sie erlaubt, Algorithmen unabhängig vom Rechner zu vergleichen: O(n) heißt, die Laufzeit wächst proportional zur Eingabe; O(n²) heißt, bei doppelter Eingabe vervierfacht sie sich. Maßgeblich ist der am stärksten wachsende Term im schlechtesten Fall (oder im Durchschnitt).