O-grande complessità di cicli for nidificati

Question

sono confuso circa la complessità dei seguenti (l'operazione eseguita all'interno del ciclo interno è in tempo costante):

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

è questo O (n^2) o O (n)? Immagino O (n^2). Qualche idea?

anche il seguente mi rende curioso:

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

Answer 1

Sicuramente O(n squared), naturalmente. Spiegazione riassuntiva per entrambi i casi: 1 + 2 + ... + n è n(n+1)/2, ovvero (n squared plus n)/2 (e in big-O lasciamo la seconda parte, minore, quindi restiamo con n al quadrato/2 che è ovviamente O(n squared)).

Answer 2

Si è corretto, quei cicli nidificati sono ancora O (n^2). Il numero effettivo di operazioni è qualcosa vicino a (n^2)/2, che, dopo aver scartato il fattore 1/2 costante, è O (n^2).