Vom Duplikat:
Titel: Es geht um die folgende Rekurrenzgleichung, da ich es nicht verstehe und kann.
Stichworte: algorithmus,gleichungen
Für a,b∈N sei die Rekurrenzgleichung T(0)=a, T(n)=T(n−1)+b für alle n∈N>0 gegeben.
Finden Sie (ohne Anwendung des Mastertheorems) eine geschlossene Form für T und zeigen Sie formal, dass T∈O(n) gilt.