Landau-Symbole
Der Algorithmus entscheidet in der Zeit formula_59, ob ein Wort der Länge formula_29 in der Sprache formula_58 liegt (vgl. Landau-Symbole zur Beschreibung der Notation). Dabei wird Speicherplatz in der Größenordnung formula_62 benötigt.