Question

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?

Comments

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 f_n = c * aⁿ.  Sollte dir das nicht gelingen, dann helfe ich dir gerne weiter.