Rekursionsgleichung mit Basisfall T (1) =1

Question

Aufgabe:

Gib für die folgende Rekursionsgleichung eine geschlossene Form in θ-Notation an. Du kannst stets von n = 2^k für k > 0 ausgehen.

T (n) = 3 * T (n - 1) + 1,   T (1) = 1

Problem/Ansatz:

T (n) = 3 * T (n - 1) + 1

= 3 * (3 * T (n -1 - 1) + 1) + 1)

= 3 * (3 * T (n - 2) + 1) + 1

= 3 * 3 * 3 ( T (n - 2 - 1) + 1) + 1) + 1

= 3 * 3 * 3 (T (n - 3) + 1) + 1) + 1)

= 3³ * T (n - 3 * 1) + $\sum\limits_{i=0}^{3-1}{3^{i}}$

n - i * 1 = 0

=> i = n

= $3^{n}$ * T ( n - 1 * n) * $\sum\limits_{i=0}^{n-1}{3^{i}}$

= $3^{n}$ * T (0) * $\sum\limits_{i=0}^{n-1}{3^{i}}$

= $3^{n}$ * T (0) * $\frac{3^{(n-1)+1}-1}{2}$

Ab hier weiß ich leider nicht weiter. Der Basisfall aus der Aufgabenstellung ist ja eigentlicht T (1) = 1. Aber ich komme hier komischerweise auf T (0).

LG

Marceline, The Vampire Queen

Answer 1

Deine Rechnungen stimmen nicht so ganz.

...= 3 * 3 * 3 ( T (n - 2 - 1) + 1) + 1) + 1=...

In dieser Zeile hast du die Klammerung nicht mehr richtig. Es muss wenn dann so hier aussehen:

$$T(n)=3\cdot T(n-1)+1\\ T(n-1)=3\cdot (n-2)+1\\ T(n-2)=3\cdot T(n-3)+1\\[10pt] T(n)=3\cdot(3\cdot(3\cdot T(n-3)+1)+1)+1$$

So deine Rekursionsgleichung zu lösen halte ich für etwas riskant, da man sich einfach zu schnell vergucken kann. Mache es stattdessen andersherum, indem du einfach mal die ersten n=1,2,3,4,5 zB mal anschaust:

$$T(2) = 3\cdot T(1)+1 = 3\cdot 1+1 = 3^1+3^0$$

$$T(3) = 3\cdot T(2)+1 = 3\cdot(3\cdot 1+1)+1 = 3^2+3^1+3^0.$$

Ich denke, ab hier sollte dann eine Struktur erkennbar sein, die du dann in eine hübsche Formel eintüten kannst, und sie nur noch per Induktion beweisen musst.

Edit: Das T(n)∈θ(3ⁿ) gilt, kannst du ja entsprechend mit der Landau-Definition nochmal verifizieren.

Comments

Tschaka hat doch t1=1 in seiner Herleitung verwendet. Du hast fälschlicherweise bei 0 angefangen zu zählen und nicht, wie es richtig ist, bei 1.

---

Danke, habs geändert.

---

@Marceline

Und wenn man es nun doch auf diese Art machen möchte, sähe das allegemein so aus:

$$T(n)=3\cdot T(n-1)+1\\ T(n-1)=3\cdot T(n-2)+1\\ T(n-2)=3\cdot T(n-3)+1\\ T(n-3)=3\cdot T(n-4)+1\\[10pt] T(n)=\underbrace{3\cdot (3\cdot (3\cdot ...\cdot 3\cdot (3}_{n-1 \text{ mal}}\cdot T(1)+1)+...+1)+1)+1\\=\underbrace{3\cdot (3\cdot (3\cdot ...\cdot 3\cdot (3}_{n-1 \text{ mal}}\cdot 1+1)+...+1)+1)+1\\=3^{n-1}+...+3^0=\sum_{k=0}^{n-1} 3^k=\frac{1}{2}\cdot (3^n-1)$$

Und wenn wir schon dabei sind, ist hier noch die Klassifikation zu der Laufzeitfunktion:

Mit n_0=1 und α=1 ergibt sich

$$0\leq T(n)=\frac{1}{2}\cdot (3^n-1)\leq 1\cdot 3^n \Leftrightarrow T(n)\in \mathcal{O}(3^n)$$

Mit n_0=1 und β=1/4 ergibt sich weiter

$$T(n)=\frac{1}{2}\cdot (3^n-1)=\frac{1}{2}\cdot 3^n-\frac{1}{2}\stackrel{n\geq 1}{\geq} \frac{1}{4}\cdot 3^n \Leftrightarrow T(n)\in \Omega(3^n)$$

Also hat man insgesamt T(n)∈Θ(3ⁿ).

Answer 2

Aloha :)

Du bist auf einem sehr guten Weg.$$t_n=3t_{n-1}+1\quad;\quad t_1=1$$Zum Entwickeln eines geschlossenen Ausdrucks für $t_n$ betrachte die ersten Folgenglieder:$$t_1=1$$$$t_2=3t_1+1=3\cdot(1)+1=3+1$$$$t_3=3t_2+1=3\cdot(3+1)+1=3^2+3+1$$$$t_4=3t_3+1=3\cdot(3^2+3+1)+1=3^3+3^2+3+1$$Jetzt kann man bereits vermuten, dass$$t_n=3^{n-1}+3^{n-2}+3^{n-3}+\cdots+3^0=\sum\limits_{k=0}^{n-1}3^k=\frac{3^n-1}{3-1}\;\;\Rightarrow\;\;\underline{t_n=\frac{3^n-1}{2}}$$Natürlich musst du das noch durch vollständige Induktion beweisen:

Verankerung bei $n=1$:$$t_1=1\quad;\quad\frac{3^1-1}{2}=1\quad\checkmark$$

Induktionsschritt $n\to n+1$:$$t_{n+1}=3t_n+1=3\cdot\frac{3^n-1}{2}+1=\frac{3\cdot(3^n-1)}{2}+\frac{2}{2}=\frac{3^{n+1}-3+2}{2}=\frac{3^{n+1}-1}{2}\quad\checkmark$$Die Laufzeit ist also von der Ordnung $\Theta(3^n)$.

Comments

Danke für die Antwort. Mich irritiert nur, dass wir ja sozusagen für die n-te Zeile den Ausdruck

= $3^{n}$ * T (0) * $\frac{3^{(n-1)+1}-1}{2}$

bzw.

= $3^{n}$ * T (0) * $\frac{3^{n}-1}{2}$ haben.

Aber in der Aufgabenstellung steht ja "Basisfall T (1) = 1." Diese Information haben wir ja jetzt gar nicht für den Lösungsweg verwendet. Ich komme hier immer auf T (0). Weil die allgemeine Form wäre ja

= $3^{i}$ * T (n - i * 1) * $\frac{3^{(i-1)+1}-1}{2}$

und T (n - i * 1) ergibt eben

n - i * 1 = 0

n = i.

Und T (n - n) wäre demnach 0. Also T (0) und nicht T (1). :(

---

Aloha :)

Direkt zu Anfang startet die Liste mit $t_1=1$. Anschließend pflanzt sich dieses $t_1$ immer weiter in die anderen $t_n$ fort. Wenn man so will, hat $t_1=1$ sogar einen Ehrenplatz.

Du numerierst die $t$'s von 0 an durch, was aber keinen Sinn macht, weil der Algorithmus für $n=0$ nichts zu tun hat, sodass $t_0=0$ sein muss.