Notación Big Oh

Question

Solo necesita una confirmación en algo muy rápido. Si un algoritmo toma n(n-1)/2 pruebas para ejecutar, ¿es el gran oh O(n^2)?

Answer 1

n (n-1)/2 se expande a (n^2 -n)/2, es (n^2/2) - (n/2)

(n^2/2) y (n/2) son los dos componentes de funciones, de los cuales n^2/2 domina. Por lo tanto, podemos ignorar la parte - (n/2).

De n^2/2 puede quitar con seguridad la/2 parte en el análisis de notación asintótica.

Esto simplifica a n^2

Por lo tanto sí, es en O (n^2)

Answer 2

Sí, eso es correcto.

n(n-1)/2 se expande a n^2/2 - n/2:

El término lineal n/2 cae porque es de orden inferior. Esto deja n^2/2. La constante se absorbe en la gran O, dejando n^2.

Answer 3

Sí:

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

Answer 4

Sí, lo es. n(n-1)/2 es (n^2 - n)/2, que es claramente menor que c*n^2 para todos n>=1 si tienes que elegir un c que es al menos 1.