Rekurrenzgleichungen

Lösen Sie die beiden folgenden Rekurrenzgleichungen und ermitteln Sie so die zugehörige Komplexitätsklasse in Abhängigkeit von $n>0$:

 

(a) Erste Rekurrenzgleichung

• $f(n) = 2 + f(n-2)$ für $n>0$
• $f(n) = 0$ für $n \leq 0$.

(b) Zweite Rekurrenzgleichung ($b \in \mathbb{R}^+$ sei eine Konstante)

• $f(n) = 2 \cdot f(n-1) + b$
• $f(1) = 1$.