Complexidade da ordenação

[Enunciado]  Queremos estudar o comportanto da função f(i) = i² + nii + n. Temos f(−1) = f(n) = 0. Além disso, a segunda derivada de f(i) é negativa. Logo, para i entre 0 e n−1, o mínimo de f(i) ocorre nos extremos do intervalo. Como f(0) = f(n−1) = n, concluímos que f(i) ≥ n para todo i no intervalo 0 .. n−1.

Podemos refazer tudo sem calcular raízes e derivadas. Como 0 ≤ in−1, temos

n−1 ≥ i
ni + 1
nii² + i
nii² − i ≥ 0
nii² − i + nn
(ni) (i + 1) ≥ n