Ansatz: a = 3, b=3, f(n)=c, jetzt muss 1ch überprüfen ob c ,= a*f(n/b) ist oder?

Question

Hallo ich hab folgende Rekusionsgleichung gegeben: 3*T(n/3)+c gegeben. Ich soll diese mit dem Mastertheorem lösen jedoch kriege ich es nicht hin.

Ansatz: a = 3, b=3, f(n)=c, jetzt muss 1ch doch überprüfen ob c > ,<,= a*f(n/b) ist oder?

Answer 1

Du musst prüfen ob

• \(f(n)\in \mathcal{O}(n^{\log_b a - \varepsilon})\) für ein \(\varepsilon > 0\) ist oder
• \(f(n)\in \Theta(n^{\log_b a})\) ist oder
  
• \(f(n)\in \Omega(n^{\log_b a+\varepsilon})\) und \(af\left(\frac{n}{b}\right)\leq df(n)\) für ein \(\varepsilon > 0\) und ein \(d\in (0,1)\) und alle hinreichend große \(n\) ist.