O(n) é solo il caso peggiore, che poi possa essere frequente un numero vicino a questo é un'altro discorso.