Informatiker Board | Algorithmen | Explizite Formel zur Rekursionsformel in O-Notation

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Explizite Formel zur Rekursionsformel in O-Notation » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Der letzte Beitrag

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.