Rekurrenz (Rekursion)



  • Hallo zusammen.
    Ich muß für meine Informatik Übung eine Aufgabe zum Thema Rekurrenz bzw. Rekursion lösen. Ich habe aber erhlich gesagt davon keine Ahnung.
    Hier die Aufgabenstellung:

    Bestimmen und beweisen Sie eine möglichst gute oberer Schranke in O-Notation für das asymptotische Verhalten der folgenden Rekursion:

    T(1)=1
    T(n)=T(n-1) + n für n>= 2

    Wäre super wenn ihr mir weiterhelfen könntet.
    MFG
    Simon



  • Lieber Simon, vielleicht würde es dir erstmal helfen zu versuchen, T(n) auch direkt (also nicht rekursiv) darzustellen.



  • Als kleiner Tipp:

    einfach mal T(1), T(2), T(3) ausrechnen. Dann die Zahlen anschauen und versuchen ein Schema zu finden. Das kann man dann anschließend mit Induktion beweisen und danach noch das O-Kalkül... fertig.

    Alternativ könnte man sich auch mal anschaun, wie

    T(n)-T(n-1) aussieht. Das dann verlängern auf T(n)-T(n-2) und so weiter bis zu T(n)-T(1) dann noch T(1) wieder aufaddieren und das Ergebnis steht da. Ist im Prinzip aber nicht anderes.

    MfG Jester




Anmelden zum Antworten