Komplexitätsklassen

Die Zahl der Elementaroperationen die zur Durchführung eines Algorithmus benötigt werden, werden mithilfe dieser Problemgröße n ausgedrückt und einer Komplexitätsklasse zugeordnet.

Die Komplexitätsklasse schaut sich nur den schnellstwachsenden Faktor an, und berücksichtigt auch dessen Koeffizienten nicht. Ein Problem der Größe 10n + 100 wird so Beispielsweise der Komplexitätsklasse O(n) zugeordnet.