Rekurrenzgleichungen lösen, Master Theorem nicht anwendbar

Question

ich habe zwei Gleichungen gegeben, welche meiner Ansicht nach, nicht mit dem Master Theorem lösbar sind.

Ich würde mich daher sehr freuen, wenn mir jemand helfen könnte diese Gleichungen zu lösen.

T(n) = T(n − 1) + O(1) 

T(n) = 7T(n/7) + n

T(n) = 2T(n/3) + 1

Answer 1

Aufgabe 2 und 3 sind auf jeden Fall per Mastertheorem lösbar! Nutze einfach die 3 Bedingungen a < , = , > b^c und du brauchst keine zwei Zeilen dafür...

Bei der ersten Gleichung kann es sich weder um logarithmischen noch exponentiellen Aufwand handeln da (n-1) linear ist und O(1) natürlich auch. O(1) bedeutet lediglich dass bei jeder Ausführung von (n-1) konstant ein Arbeitsschritt mehr benötigt wird.