Zeitkomplexitätsklassen

Drei zentrale Zeitkomplexitätsklassen werden unterschieden:

Algorithmus A heißt:

linear-zeitbeschränkt fA ? O ( n )

polynomial-zeitbeschränkt ? k ? N, so daß

fA ? O ( nk ) .

exponentiell-zeitbeschränkt ? k ? N , so daß

fA ? O ( kn ).