nicht rekursive Funktion als obere Abschätzung gesucht

Question

Aufgabe:

\( F(1)=1 \) und \( F(n)=2 \cdot F\left(\left\lfloor\frac{n}{2}\right\rfloor\right) \cdot F\left(\left\lfloor\frac{n}{2}\right\rfloor\right) \) für \( n>1 \)

es ist eine Funktion g: R+ -> R+ gesucht, die eine obere Abschätzung von F ist und nicht rekursiv definiert ist.

Problem/Ansatz:

Ich habe bisher nur raus, dass die Funktion 2^n schneller wächst als F.

Answer 1

richtig ist F(2^n)=2^n-1 also kannst du damit die sicher größere Funktion nennen , von 2^n bis 2n+1 ist die Funktion konstant,

Gruß lul

Comments

Hallo,

ich bin mir jetzt unsicher, kann ich also vermuten, dass F in O(2^n) liegt ?

---

versteh ich nicht, du suchst eine Funktion keine Funktionenklasse? was soll also das  in O(2^n) sagen?

lul