Zeitkomplexität Fibonacci Algorithmus Obergrenze: T(n) <= 2^n, für alle n >= 0

Question

Aufgabe:

Wenn man einen einfachen Fibonacci Algorithmus hat mit:

$$F_0 = 0\\ F_1 = 1\\ F_n = F_{n-1} + F_{n-2} \quad \text{for } n \geq 2$$

Wie beweißt man folgende Obergrenze für die Zeikomplexität ?

$$T(n) \leq 2^n \text{ für alle}   n \geq 0$$

Problem/Ansatz:

$$\text{Anfang:  } T(0) =  1 \text{und } 2^0 = 1 $$

Dann:

$$\text{[1]    } T(n) = 2^{n-1}+2^{n-2}+1 \leq 2^n$$

Und soweit ich weiß, sollte das der nächste Schritt sein.
$$\text{[2]    } 2^{n-1}+1 \leq 2^{n-1} \quad \text{      dasteht. }$$

Ich kann diesen Schritt nicht nachvollziehen. Hab alle Potenzgesetze die ich kenne rausgekramt, aber komme einfach nicht  von [1] nach [2]. Und verstehe auch nicht wie mir der Anfang weiterhelfen könnte.

Answer 1

Hallo
dein 2. ist einfach falsch! a+1<a ist immer falsch. aber voeööeocj hast du dich vertippt?

2ⁿ⁻²+1≤2 ⁿ⁻¹

2^n=2^n-1+2^n-1=2^n-1+2^n-2+2^n-2 >2^n-1+2^n-2+1; für n>2

Gruß lul

Comments

Vielen Dank, ja du hast recht. da sollte 2^{n-2} +  1 auf der linken Seite stehen.
kannst du mir sagen, warum man das hier machen darf ?
2^{n}=2^{n-1}+2^{n-1}

---

2^n=2*2^n-1=(1+1)2^n-1

Gruß lul