Die Funktion f : N -> N sei definiert durch:

f(n) = Summe(i=0 bis 3) (n über i).

Zeige: f(n) ist O(n³)

??? Sei n = 2

(2 ü 0) + (2 ü 1) + (2 ü 2) + (2 ü 3)
1 + 2 + 1 + 1 = 5

Wo ist denn hier jetzt irgendeine Ordnung und wo ist diese 8?

bist dus icher dass das ganze nicht ab n>= 3 gilt??? summe (2 ueber 3) sieht doch sehr merkwuerdig aus

Na ja. Ist eine Klausurmitschrift. Aber hmm. Mit 3 wären das dann halt 1+3+3+1 = 8 und 3³ = 27. Ich weiß ja hier noch nicht einmal ob das Ergebnis überhaupt etwas mit der Ordnung zu tun hat. :L

darf ich fragen zu welcher klausurmitschrift das gehoert? welches jahr

edit: hab sie gefunden

Die Funktion f : N -> N sei definiert durch:

f(n) = Summe(i=0 bis 3) (n über i).

Zeige: f(n) ist O(n³)

??? Sei n = 2

(2 ü 0) + (2 ü 1) + (2 ü 2) + (2 ü 3)
1 + 2 + 1 + 1 = 5

Wo ist denn hier jetzt irgendeine Ordnung und wo ist diese 8?

f(n) = (n ü 0) + (n ü 1) + (n ü 2) + (n ü 3) = 1 + n + n*(n-1) + n*(n-1)*(n-2) = lauterkleinkram + irgendwas * n^3 -> f(n) liegt in O(n^3)

(ausmultiplizieren darst du selber ;) )