Asymptotisches Wachstum einer Rekursionsgleichung

Question

Aufgabe:

Gib für die folgende Rekursionsgleichung eine geschlossene Form in θ-Notation an. Du kannst stets davon ausgehen, dass n eine Potenz von 4 und n ≥ 4 ist

T (0) = 2,   T (n) =  T (n - 4) + 8 für n ≥ 1

Problem/Ansatz:

T (n) =  T (n - 4) + 8

= T (n -4 - 4) + 8 + 8

= T (n - 8 - 4) + 8 + 8) + 8

= T (n - 12) + 8 + 8) + 8)

= (T (n - 4 * i) + 8) + 8) + 8)

=  T (n - 3 * 4) + \( \sum\limits_{i=0}^{k}{8} \)

n - i * 4 = 0

=> i = \( \frac{n}{4} \)

=  T ( n - 4 +\( \frac{n}{4} \) ) * \( \sum\limits_{i=0}^{k}{8} \)

=  T (0) * \( \sum\limits_{i=0}^{\frac{n}{4}}{8} \)

=  2 + \( \sum\limits_{i=0}^{\frac{n}{4}}{8} \)

Ab hier weiß ich leider nicht weiter, bzw. weiß nicht, ob ich richtig gerechnet habe.

LG

Marceline, The Vampire Queen

Comments

Meiner Meinung nach ist mit T (0) = 2,  T (n) =  T (n - 4) + 8 für n ≥ 1 die Folge der Geraden Zahlen festgelegt.

---

Danke für die Antworten, Roland. Wie kommst du darauf, dass es die geraden Zahlen sind? Weil +8)+8)+8) ist ja eigentlich 8,16,24 usw. Also die Summe von 8er-Zahlen.

---

Jede vierte Zahl der Folge ist um 8 größer. Das geht nur so:

n	0	1	2	3	4	5	6	7	8
T(n)	2	4	6	8	10	12	14	16	18

Answer 1

Aloha :)

$$T(n)=T(n-4)+8\;\;;\;\;n\ge1\quad;\quad T(0)=2$$Um eine Idee für den gesuchten Ausdruck zu erhalten, schreiben wir die ersten Terme einfach mal auf:$$T(0)=2$$$$T(4)=T(4-4)+8=T(0)+8=2+8$$$$T(8)=T(8-4)+8=T(4)+8=2+8+8$$$$T(12)=T(12-4)+8=T(8)+8=2+8+8+8$$Mit der Annahme, dass n ein Vielfaches von 4 ist, also \(n=4\cdot k\;;\;k\ge0\), lesen wir folgende Vermutung ab:$$T(4k)=2+8\cdot k\quad;\quad k\ge0$$Diese beweisen wir durch vollständige Induktion:

Verankerung bei \(k=0\):$$T(4\cdot0)=2+8\cdot0=2\quad;\quad T(0)=2\quad\checkmark$$Induktionsschritt für \(k\to k+1\):$$T(4(k+1))=T(4k+4)=T(4k)+8\stackrel{I.V.}{=}(2+8\cdot k)+8=2+8\cdot(k+1)\quad\checkmark$$Wegen \(n=4k\) ist \(k=\frac{n}{4}\) und es gilt:$$T(n)=T(4k)=2+8\cdot k=2+8\cdot\frac{n}{4}=2+2\cdot n\quad\Leftrightarrow\quad\underline{T(n)=2(n+1)}$$

Comments

Danke für die ausführliche Antwort, Tschakabumba.

Haben selbst noch ein bisschen rumprobiert und die Lösung durch rekursives Einsetzen gefundet. Läuft aber auf dasselbe raus, wie bei dir. Vielen Dank!

T (4 - 4) + 8

= 2 + 8

= 10.

=> 2n + 2

Nächste 4er-Potenz

T (16 - 4) + 8

T (12) + 8

T (8) + 8 + 8

T (4) + 8 + 8) + 8)

T (0) + 8) + 8) + 8) + 8

= 2 + 8 + 8 + 8 + 8

= 34

=> 2n + 2

T (64 - 4) + 8

T (60 - 4) + 8 + 8

... T (0) + 16 * 8

2 + 16 * 8

= 130

=> 2n + 2

Das +2 und das "2*" asymptotisch vernachlässigen => Laufzeit (n).