Frage zu groß-O Notation.
-
Wenn die Funktion ist.
Ist dann die Funktion
-
Sorry, latex geht wohl nicht, drum:
Wenn die Funktion f(n) = O(n) ist.
Ist dann die Funktion
Summe von k=0 bis n von f(n) = O(n^2) ?
Wie beweist man sowas ?
-
Ja, das gilt. Da f(n) = O(n) gibt es ein c>0 und ein n_0 so dass für alle n>=n_0 gilt: f(n) <= c * n
Jetzt zerlegst Du Deine Summe in zwei Teile:
Den Teil k=0...n_0-1 und den von n_0 bis n.
Der erste Teil bildet eine Konstante. Im zweiten Teil kannst Du das f(n) durch c*n abschätzen, der Rest ist dann klar, oder?
-
Jester schrieb:
Ja, das gilt. Da f(n) = O(n) gibt es ein c>0 und ein n_0 so dass für alle n>=n_0 gilt: f(n) <= c * n
Jetzt zerlegst Du Deine Summe in zwei Teile:
Den Teil k=0...n_0-1 und den von n_0 bis n.
Der erste Teil bildet eine Konstante. Im zweiten Teil kannst Du das f(n) durch c*n abschätzen, der Rest ist dann klar, oder?Danke dir!