0 Daumen
58 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

Gefragt 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).

Beantwortet von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...