Algoritmi - calcolo complessità

Salve,

sta mattina ho dato l'esame di IP e mi è stato chiesto di calcolare la complessità nel caso peggiore della seguente funzione:

void r(vector<int> & v, int n) {
    int i=0;
    while (i<v.size()) {
    if (v[i]>n) {
         for (int j=i+1; j<v.size(); j++) v[j-1]=v[j];
         v.resize(v.size()-1);
    } 
    else i++;
    }
}

N è la dimensione del vettore.
I miei calcoli mi hanno portato a stimarne una complessità quadratica, mentre in teoria (secondo le soluzioni) dovrebbe essere lineare.
Qualcuno sa darmi qualche delucidazione? Grazie

anche se ci sono due cicli annidati, il ciclo interno contiene una resize, ovvero una funzione che riduce la lunghezza del vettore ad ogni iterazione

HeDo, ha ragione lui. Nel caso pessimo, ossia quando l'array è costituito da elementi sempre maggiori di n, la complessità è quadratica.
Infatti, in questo caso, il contatore i non viene mai incrementato, ma solo la dimensione dell'array diminuisce. Ciò significa che se i inizia da 0, alla prima iterazione del while il for interno farà size - 1 iterazioni, poi size - 2, poi size - 3, eccetera... Calcolando la somma di questa serie aritmetica si ottiene una complessità pari a size * (size - 1) / 2.
Ho anche fatto una simulazione per essere sicuro e i risultati combaciano.