Explizite Formel zur Rekursionsformel in O-Notation

Neue Frage »

Auf diesen Beitrag antworten »
chiller Explizite Formel zur Rekursionsformel in O-Notation

Meine Frage:
Hallo,

ich muss eine explizite Formel zu folgenden Rekursionsformel herleiten:

[latex]T(n) <=  c  [/latex]
bei c ist n=1
[latex]T(n) <=  4T(n/2)+cn [/latex]
bei der Formel n>1


Meine Ideen:
Ich bin durch das einsetzen auf diese Formel gekommen:

[latex]i^2T(\frac{n}{i})+\frac{3}{4} icn+cn [/latex]

Ist diese richtig? Wenn ja, wie komme ich denn von dieser Formel auf eine O-Notation?

Durch Raten bin ich auf das hier gekommen:
[latex]nT(1)+O(n)+O(n)[/latex]
Bitte fragt mich nicht wie ich auf die O-Notation gekommen bin. Ist halt nur geraten.

Ich danke euch schon mal für eure Hilfe.
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »