Třídy složitosti
Pro funkci f : ℕ → ℕ rozumíme třídou časové složitosti Τ(f(n)), množinu těch problémů, které jsou řešeny RAMy s časovou složitostí v O(f).
Třídou prostorové složitosti S(f), též S(f(n)), rozumíme třídu těch problémů, které jsou řešeny RAMy s prostorovou složitostí v O(f).