n(n-1)/2 expands to (n^2 -n) / 2
, that is (n^2/2) - (n/2)
(n^2/2)
and (n/2)
are the two functions components, of which n^2/2
dominates.
Therefore, we can ignore the - (n/2)
part.
From n^2/2
you can safely remove the /2 part in asymptotic notation analysis.
This simplifies to
n^2
Therefore yes, it is in O(n^2)
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…