Big-Oh Notation
Yes:
n(n-1)/2 = (n2-n)/2 = O(n^2)
Yes, it is. n(n-1)/2
is (n^2 - n)/2
, which is clearly smaller than c*n^2
for all n>=1
if you pick a c
that's at least 1.
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)
Yes, that is correct.
n(n-1)/2
expands to n^2/2 - n/2
:
The linear term n/2
drops off because it's of lower order. This leaves n^2/2
. The constant gets absorbed into the big-O, leaving n^2
.