wieso $n^p + n^q$ und nicht $n^{pq}$?

Question

Hallo,

wieso ist die Verkettung aus $g$ und $f$ nicht $(n^p)^q = n^{pq}$ sondern $n^p + n^q$? Wenn $f= x^2$ ist und $g =x^3$, dann ist die verkettung auch $x^6$.

Viele Grüße

Answer 1

Es muss tatsächlich gelten $h \in O(n^{pq})$. Ihre Argumentation is korrekt, denn $g$ operiert nicht auf $n$, sondern auf $f(n)$, und $f(n)$ kann eine bis zu polynomiell größere Eingabe sein als $n$.

Einen formellen Beweis für den allgemeinen Fall, wenn $f$ und $g$ einer beliebigen Wachstumsklasse angehören, finden Sie hier. Der allgemeine Fall ist sogar noch ein bisschen komplizierter.

Wir werden die Lösung enstprechend anpassen und eine überarbeitete Version hochladen.

Marlon Braun (Übungsleiter)