CODEWITHSUNDEEP
algorithmbig-ograph-theorybreadth-first-search
Uttakarsh Tikku
Uttakarsh Tikku

Reputation: 23

What is the complexity of breadth first search for a complete graph?

The complexity of BFS is said to be linear ie., O(V+E) but the total number of edges in a directed complete graph are V*(V-1) which is a degree 2 function of the size of the graph. So would the BFS take O(V^2) time to traverse through a complete graph?

Upvotes: 1

Views: 2904

Answers (2)

user2736738
user2736738

Reputation: 30906

BFS runs in O(V + E) time provided the graph is represented by the adjacency list structure.

In the dense case also, you will see the answer will be O(V+E). (Representation is adjacency list).

In case of Adjacency matrix O(V^2).

No matter how the graph is , you will always first cover the neighbor of the starting point. Then repeat this for the neighbors too. So you can see that it will always have to traverse in O(V+E) time but it is the representation that makes it hard for adjacency matrix. So it will be O(V^2)1.

1This is because every time we want to find what are the edges adjacent to a given vertex 'u', we traverse the whole array adjmatrix[u], which is of length |V|

Upvotes: 1

Conrad Parker
Conrad Parker

Reputation: 844

Yes, I assume you already did the math.

O(V+E) = O(V + V*(V-1))
       = O(V + V*V - V)
       = O(V*V)

Upvotes: 2

Related Questions