Herleiten der expliziten Formel aus der Rekursionsformel

ChillStudent

Mitglied
Hallo,
die Aufgabe lautet :

Leiten Sie zur Rekursionsformel
Code:
          c               n = 0
T(n) ≤ 
          T(n−1) +cn      n > 1
die explizite Formel in O-Notation her.

Lösungvorschlag:
Code:
T(n) ≤ 2T((n/2)-1)+2cn
T(n) ≤ 4T((n/4)-1)+4cn
T(n) ≤ 8T((n/8)-1)+8cn
...
T(n) ≤ 2^iT((n/2^i)-1)+(2^i)cn
...

hoffe soweit richtig?
Mein Problem ist jetzt, daraus die O-Notation zu erstellen...
Habe mir gedacht...
Code:
nT(0)+n²=O(n²)
bin mir sehr unsicher was die Notation angeht :/
 
Für Anfänger vielleicht, mit Java hat das jedoch wohl eher gar nichts zu tun 😉

Zum Thema:

Du musst wenigstens die Aufgabe korrekt abtippen. Was soll denn für n=1 passieren?
Und soll da wirklich ein "kleiner-gleich" stehen und nicht einfach eine Fallunterscheidung?
Wenn die Aufgabe so lautet, wie ich vermute, dann solltest du am Ende auf eine quadratische Laufzeit kommen. Bevor das aber nicht geklärt ist, hab ich jedoch keine Lust groß rumzuraten.
 

Neue Themen


Zurück
Oben