Złożoność algorytmu

Question

Mam za zadanie udowodnić, że f(n)= n(n+1)/2 jest O(n^2).
Czy zapisanie: f(x)=n(n+1) => f(x)=n*(n) => f(x) = n^2 => O(n^2), jest poprawne i wystarczy?

Answer 1

Niestety wydaje mi się, że przykład jest zbyt prosty, żeby można było po prostu powiedzieć, że to oczywiste, bo to właśnie zrobiłeś :P.

Powołałbym się zatem na definicje O(), gdzie jest napisane pieknym językiem matematycznym, ze f(n) jest O(g(n)) jesli od pewnego n0 f(n) <= c*g(n) dla dowolnego c >0

Nasze równanie wyglada zatem tak:

n(n+2)/2=0.5n^2 + n = O(n^2) + O(n^2) //nawet O(n) ale na potrzeby obliczen przyjmiemy nawet n^2

https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu#Uwagi :

Suma funkcji f1 i f2 O(g(n)) tez jest O(g(n)) jeśli f1*f2 jest O(g^2(n)):

n^4 <= n^4