Aus der vorherigen Betrachtung wissen wir, wie wichtig die Komplexitätsklasse \(P\) und damit Polynome sind. In der Praxis sind die genauen konstanten Faktoren im Polynom aber oft nicht interessant. Ebenso sind oft die Summanden mit kleinerem Exponenten meist nicht von Interesse. So interessiert bei einem Polynom wie \(n^3 + 2 \cdot n^2 – 5 \cdot n\) oft nur, dass es sich „grob so verhält wie \(n^3\)„. Um dies zu formalisieren, wird die Landau-Notation oder \(O\)-Notation eingeführt, die insb. auch in der Algorithmik zum Vergleich verschiedener Algorithmen von großer Bedeutung ist. Wir wollen uns hier nicht näher mit der \(O\)-Notation beschäftigen und wollen uns nur folgendes merken:

Dies ist deswegen praktisch, da man dann bei einem Algorithmus, der z.B. bei \(n\) Zahlen alle Zahlen paarweise miteinander vergleicht, sagen kann, dass er eine Laufzeit in \(O(n^2)\) hat, obwohl neben den \(n^2\) Vergleichen vielleicht noch Dinge passieren, wie eine Schleifenvariable zu erhöhen und ähnliches. So lange dies nur konstant viele Operationen sind, die pro Vergleich passieren, ist die Laufzeit in \(c \cdot n^2\) für eine Konstante \(c\) und damit in \(O(n^2)\).

Oft benutzt man dann in der Algorithmenanalyse auch nicht mehr die Eingabelänge \(n\), sondern eine Kenngröße \(n\), aus der sich die eigentliche Eingabelänge leicht ermitteln lässt und die aber i.A. aussagekräftiger ist. Hat man z.B. einen Algorithmus auf Graphen, so nimmt man als Kenngröße oft die Anzahl der Knoten \(n\) und die Anzahl der Kanten \(m\) und drückt die Laufzeit dann bzgl. dieser Kenngrößen aus.