Is for each u,v in V loop linear on V?

Question

Knowing that

for each u in V do // O(V)
     // ...

Does this loop:

for each u,v in V do // O(V) or O(V^2)?
     // ...

is linear on V or V^2?

Answer 1

It’s O(V²). More generally, there are Θ(n²) pairs that can be made from a set of n items, and if you iterate over all them it’ll take quadratic time simply listing them out.