0 Daumen
227 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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

Gruß lul


Avatar von 106 k 🚀

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community