CODEWITHSUNDEEP
algorithmdata-structuresgraphcomplexity-theory
ٍSofyan Mahmoud
ٍSofyan Mahmoud

Reputation: 326

How many edges in dense graph

I have read that in the dense graph, the number of edges is (n^2) and I don't know-how If I have a graph and every node connected to other all nodes then the number edges will be ( (n-1) + (n-2) + (n-3) + ..... + 1) so, how the edges in dense graph are (n^2)

Upvotes: 0

Views: 1168

Answers (2)

thienDX
thienDX

Reputation: 294

It's the Big O notation, maybe what they mean is the complexity when you do a graph traversal. In Big O notation : O(n²/2) = O(n²)

Upvotes: 4

Svante
Svante

Reputation: 51531

It depends on whether your graph is directed. In an undirected dense graph, the number of edges is (n · (n − 1) / 2) (which is equal to your series). In a directed graph, the number is double that, so just (n · (n − 1)).

This is not exactly (n²), but very close to it. You can say that n² is an upper bound, so it is maybe more appropriate to say O(n²) if that makes sense in the context.

Upvotes: 4

Related Questions