Big-O complejidad de anidado para bucles

Question

estoy confundido acerca de la complejidad de los siguientes (la operación realizada en el interior del bucle interno es en tiempo constante):

for(int i=0; i<n; i++) 
    for(int j=i; j<n; j++) 

es este O (n^2) o O (n)? Me imagino O (n^2). ¿Algunas ideas?

también los siguientes me hace curioso:

for(int i=0; i<n; i++) 
    for(j=0; j<i; j++) 

Answer 1

Definitivamente O(n squared), por supuesto. Explicación resumida para ambos casos: 1 + 2 + ... + n es n(n+1)/2, es decir, (n squared plus n)/2 (y en big-O caemos la segunda parte, menor, por lo que nos queda n cuadrado/2, que es por supuesto O(n squared)).

Answer 2

Tiene razón, esos bucles anidados siguen siendo O (n^2). El número real de operaciones es algo cercano a (n^2)/2, que, después de descartar el factor constante 1/2, es O (n^2).