Herleiten der expliziten Formel aus der Rekursionsformel

[ChillStudent]

Hallo,
die Aufgabe lautet :

Leiten Sie zur Rekursionsformel

          c               n = 0
T(n) ≤ 
          T(n−1) +cn      n > 1

die explizite Formel in O-Notation her.

Lösungvorschlag:

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...

nT(0)+n²=O(n²)

bin mir sehr unsicher was die Notation angeht :/

 

[Sogomn]

Bist du ganz sicher, dass da Java für Anfänger ist?

 

[kaoZ]

Das fällt eher unter Mathematik

und auch dafür gibt es hier ein Unterforum

 

[stg]

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.