Wie mach ich das, bzw. wie gehe ich da jetzt vor habe nämlich kein Plan wie ich das "Zeigen/Beweisen" soll...
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).
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos