0 Daumen
195 Aufrufe

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?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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.
Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community