Grundlagen

Die Komplexität oder synonym Kosten eines Algorithmus werden durch Zeit und Platz beschrieben. Bei den Effizienten Algorithmen steht meist die Analyse des Zeitbedarfs im Vordergrund, so dass im Folgenden mit ''Kosten'', soweit nicht explizit angegeben, die Laufzeit impliziert wird.

Landau-Symbole zur Abschätzung der Komplexität:
- $f(n)=O(g(n))$: die Funktion $f(n)$ wächst höchstens so schnell wie $C \cdot g(n)$
- $f(n)=\Omega(g(n))$: die Funktion $f(n)$ wächst mindestens so schnell wie $C \cdot g(n)$
- $f(n)=\Theta(g(n))$: die Funktion $f(n)$ wächst genauso schnell wie $C \cdot g(n)$
- $f(n)=o(g(n))$: die Funktion $f(n)$ wächst echt langsamer als $C \cdot g(n)$
- $f(n)=\omega(g(n))$: die Funktion $f(n)$ wächst echt schneller als $C \cdot g(n)$

Typische verschiedene Ordnungen sind aufsteigend:
$O(1)$: konstant, $O(\log n)$: logarithmisch, $O(n)$: linear, $O(n^2)$: quadratisch, $O(n^3)$: kubisch
$O(x^k)$: polynomial, $O(k^x)$: exponentiell ($k$ jeweils konstant)

Die Basis eines Logarithmus ändert nichts an der Ordnung, da $\log_B x = \frac{\log_e x}{\log_e B}$.

Notation:
Soweit nicht explizit angegeben, sei im Folgenden $\log x = \log_2 x$.