0 Daumen
331 Aufrufe

Wie mach ich das, bzw. wie gehe ich da jetzt vor habe nämlich kein Plan wie ich das "Zeigen/Beweisen" soll...


Bild Mathematik

Avatar von

1 Antwort

0 Daumen

Du must schauen dass du eine Zahl c findest, so dass das was auf der linken Seite steht kleiner oder gleich dem c-fachen dessen ist, was auf der rechten Seite in der Klammer steht; und zwar egal welchen Wert n hat. Dabei darfst du n > [irgendeine Zahl] annehmen.

b) Für n>0 ist n(n-1)/2 = 1/2 n2 - n/2 ≤ 1/2 n2.

Es kann also c=1/2 gewählt werden.

Also ist n(n-1)/2 in O(n2).

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community