Big-O complexity for this loop

Question

What's the big-O complexity for the following loop:

for each vertex u ∈ C do
        for each vertex v ∈ C and v > u do

What I'm doing here is imagine the following set {1,2,3,4} the loop executes a function for all the combinations of 2 elements of this numbers, (1,2), (1,3), (1,4), (2,3), (2,4), (3,4).

Is it =(n^2) where n is the number of elements in the set?

Answer 1

Yes, this is O(n^2), assuming the function executed is O(1), of course, and the iterator is also O(1) on average per iteration (which is usually a valid assumption).

Note that even if you optimize it further, you are going to process Choose(n,2) elements, and Choose(n,2)=n(n-1)/2, which is still in O(n^2).

Answer 2

Hint: write an equation describing the number of combinations as a function of the size of the set.

Drop any lower-order terms and ignore any constant multipliers in your highest-order term.