Im Einzelfall wird man den Aufwand einfach messen,  aber um für weitere Einsätze eine Vorhersage machen zu können, sollte man etwas über die Abhängigkeit des Aufwandes von der Problemgröße wissen, zumal dann, wenn mehrere Verfahren zur Auswahl stehen. Man wird also versuchen, den Aufwand zu berechnen. Dies kann sehr detailliert geschehen und ist dann oft sehr schwierig; oft genügen aber schon globale Aussagen der Art, wie stark der Aufwand mit der Problemgröße wächst, und sie sind oft recht einfach zu erhalten. Eine solche asymptotische Abschätzung ist recht grob und nur bis auf einen konstanten Faktor bekannt, dennoch kann sie zur Auswahl eines geeigneten Verfahrens ausreichen.

Um über das Wachstumsverhalten von Funktionen reden zu können, definieren wir:

Die Größenordnung einer Funktion f: NN ist die Menge der Funktionen g, die schließlich nicht schneller anwachsen  als f:

(f) = { g: NN | c>0 n0 mit g(n) <= c*f(n) n >= n0 }

f(n) ist also für genügend große n bis auf einen konstanten Faktor c eine obere Schranke  für g(n).

• g(1) : g hat konstanten Aufwand 
• g(log n) : g wächst logarithmisch 
• g(n) : g wächst linear 
• g(n**k) für ein k > 1 : g wächst polynomiell 
• g(a**n) für ein a > 1 : g wächst exponentiell 
• es gilt: (1) (log n) (n) (n**k) (a**n)