Big Oh notation

Question

Basta avere una conferma su qualcosa di veramente veloce. Se un algoritmo richiede i test n(n-1)/2 per eseguire, è il grande oh O(n^2)?

Answer 1

n (n-1)/2 si espande a (n^2 -n)/2, cioè (n^2/2) - (n/2)

(n^2/2) e (n/2) sono le due funzioni componenti, di cui domina n^2/2. Pertanto, possiamo ignorare la parte - (n/2).

Da n^2/2 è possibile rimuovere in modo sicuro la parte/2 nell'analisi di notazione asintotica.

Questo semplifica al n^2

Pertanto sì, è in O (n^2)

Answer 2

Sì, è corretto.

n(n-1)/2 espande a n^2/2 - n/2:

Il termine lineare n/2 cade perché è di ordine inferiore. Questo lascia n^2/2. La costante viene assorbita nel Big-O, lasciando n^2.

Answer 3

Sì:

n(n-1)/2 = (n2-n)/2 = O(n^2) 

Answer 4

Sì, lo è. n(n-1)/2 è (n^2 - n)/2, che è chiaramente più piccolo di c*n^2 per tutti n>=1 se si sceglie un c che è almeno 1.