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

Wed, 03 Jan 2018 09:40:04 +0000

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)

Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-3-3

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