Landau-Symbole
Die Komplexität wird häufig mit Hilfe der Landau-Symbole beschrieben, um von Eigenheiten bestimmter Implementierungen und Berechnungsmodelle zu abstrahieren. Die Schwierigkeit bei der Bestimmung der genauen Komplexität eines Problems liegt darin, dass man hierfür sämtliche mögliche Algorithmen betrachten müsste. Man muss also beweisen, dass ein bestimmter Algorithmus "optimal" für dieses Problem ist.