f(n)
1 + (2+n)(3+n) + 4
TERM-WERKSTATT
Streichen vor Schätzen.
07 / 17
Mission
Vereinfache zuerst k(n). Danach entscheidest du vier Big-O-Aussagen mit je einem Satz.
Big-O heißt hier: „wächst höchstens so schnell wie“.
f(n) = 1 + (2+n)(3+n) + 4
g(n) = 2n + 3n − 4n
h(n) = (17+n1,99) · 242 · log2(n)
k(n) = n² + 2n² − 3n²
Dein erster Zug
Tippe die drei Koeffizienten von k(n) an, um sie zusammenzufassen.
Alle drei Summanden haben denselben Faktor n². Sammle nur die Zahlen davor.
Rechne 1 + 2 − 3. Erst danach darfst du die Wachstumsordnung benennen.
Vier Terme, vier Wachstumskarten
Ordne jeder Funktion ihren dominanten Term zu. Genaues Kürzen kommt vor Big-O.
g(n)
2n + 3n − 4n
h(n)
(17+n1,99)·242·log₂n
k(n)
n² + 2n² − 3n²
Vier Aussagen vor Gericht
Wähle wahr oder falsch. Deine Begründung entsteht danach als prüfungstauglicher Satz.
Vergleiche nur: n, n², n1,99log n und 0. Ein Logarithmus macht den fehlenden Polynomfaktor n0,01 asymptotisch nicht wett.
O(g)·O(g) wächst hier wie n·n = n². Für (4): Die Nullfunktion liegt unter jeder positiven asymptotischen Schranke.
Prüfungsabschluss
Jetzt erst darf der vollständige Musterweg sichtbar werden.
Vorarbeit: f(n)=n²+5n+11 ∈ Θ(n²), g(n)=n ∈ Θ(n), h(n) ∈ Θ(n1,99log₂n), k(n)=0.
- Wahr: g ∈ O(f), da lineares Wachstum durch quadratisches Wachstum nach oben beschränkt wird.
- Wahr: f ∈ O(g)·O(g), da O(n)·O(n)=O(n²) gilt und f quadratisch wächst.
- Falsch: f ∉ O(h), da n² schneller wächst als n1,99log₂n; insbesondere n0,01/log₂n → ∞.
- Wahr: k ∈ O(f), da k(n)=0 ist und die Nullfunktion von f nach oben beschränkt wird.