0 Daumen
599 Aufrufe

Datenstruktur mit oberen Schranken

Gegeben sei folgende Zahlenfolge:
fn = fn..2 + fn..4 falls n > 4,
fn = 1 sonst.
Zeigen Sie eine exponentielle obere Schranke für fn.


Meine Idee ist es da wir eine exponentielle obere Schranke suchen müsste normal O(n*log n) rauskommen oder?

Avatar von

Tipps:

- Schreibe die Formeln so, dass man sie lesen kann.

- Schreibe die ersten 20 Glieder explizit hin.

- Was hat O(n log n) mit exponentiellem Wachstum zu tun?

Hallo User1994, bitte geh mal wie von Fakename beschrieben vor.  Wenn du damit fertig bist, versuche eine Abschätzung mit fn = c * an.  Sollte dir das nicht gelingen, dann helfe ich dir gerne weiter.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community