O Notation - Aussagen Beweisen?

Question

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

Answer 1

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 n² - n/2 ≤ 1/2 n².

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

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