ERST KÜRZEN, DANN VERGLEICHEN
Big-O ohne Ratespiel
06 / 17
Deine Mission
Entzerre vier Funktionen. Erst danach entscheidest du fünf Big-O-Aussagen — jeweils mit genau einem Satz.
Erster Zug: Welcher Term dominiert bei f(n)?
f(n) = 1 + 2n + 3n + 4
g(n) = (1+n)(2+n) − 3n
h(n) = (17+n²) · log₃(n)
k(n) = 42 + n² + (1+n)(2−n)
Term-Werkstatt
Bearbeite immer nur den leuchtenden Term. Ausmultiplizieren und Kürzen kommt vor Big-O.
Big-O-Duell
Übersetzung:
a ∈ O(b) heißt: „a wächst höchstens so schnell wie b.“
Links darf kleiner oder gleich schnell wachsen — aber nicht schneller.
Wähle wahr/falsch und formuliere deinen Ein-Satz-Grund. Bewertet wird die eindeutige Auswahl; dein Satz bleibt dein Prüfungsbeleg.
Prüfungsabschluss
Der vollständige Musterweg bleibt gesperrt, bis du alle fünf Aussagen versucht hast.
Dominante Terme
f(n)=5n+5 ∈ Θ(n)g(n)=n²+2 ∈ Θ(n²)h(n)=(n²+17)log₃(n) ∈ Θ(n² log n)k(n)=n+44 ∈ Θ(n), denn die beidenn²-Terme löschen sich.
Fünf klausurfertige Sätze
- Falsch:
g ∉ O(f), weil quadratischesgschneller wächst als linearesf. - Wahr:
g ∈ O(f)·O(f), weil das Produkt zweier linearer Schranken quadratisch ist und damitgbeschränkt. - Wahr:
g ∈ O(h), weiln²höchstens so schnell wächst wien² log n. - Falsch:
h ∉ O(g), weil der zusätzliche Faktorlog nunbeschränkt wächst. - Falsch:
g ∉ O(k), weilknach dem Kürzen linear,gaber quadratisch ist.
Wie sitzt es?
Noch nicht markiert.