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.
|