CODEWITHSUNDEEP
algorithmtime-complexitybreadth-first-search
RookieCookie
RookieCookie

Reputation: 312

Time Complexity Analysis of BFS

I know that there are a ton of questions out there about the time complexity of BFS which is : O(V+E)

However I still struggle to understand why is the time complexity O(V+E) and not O(V*E)

I know that O(V+E) stands for O(max[V,E]) and my only guess is that it has something to do with the density of the graph and not with the algorithm itself unlike say Merge Sort where it's time complexity is always O(n*logn).

Examples I've thought of are :

  1. A Directed Graph with |E| = |V|-1 and yeah the time complexity will be O(V)
  2. A Directed Graph with |E| = |V|*|V-1| and the complexity would in fact be O(|E|) = O(|V|*|V|) as each vertex has an outgoing edge to every other vertex besides itself

Am I in the right direction? Any insight would be really helpful.

Upvotes: 4

Views: 1797

Answers (4)

RBarryYoung
RBarryYoung

Reputation: 56725

It depends on how the adjacency list is implemented. A properly implemented adjacency list is a list/array of vertices with a list of related edges attached to each vertex entry.

The key is that the edge entries point directly to their corresponding vertex array/list entry, they never have to search through the vertex array/list for a matching entry, they can just look it up directly. This insures that the total number of edge accesses is 2E and the total number of vertex accesses is V+2E. This makes the total time O(E+V).

In improperly implemented adjacency lists, the vertex array/list is not directly indexed, so to go from an edge entry to a vertex entry you have to search through the vertex list which is O(V), which means that the total time is O(E*V).

Upvotes: 0

Hikmat Farhat
Hikmat Farhat

Reputation: 592

The complexity comes off easily if you walk through the algorithm. Let Q be the FIFO queue where initially it contains the source node. BFS basically does the following

while Q not empty
  pop u from Q
  for each adjacency v of u
     if v is not marked
         mark v
         push v into Q

Since each node is added once and removed once then the while loop is done O(V) times. Also each time we pop u we perform |adj[u]| operations where |adj[u]| is the number of adjacencies of u.

Therefore the total complexity is Sum (1+|adj[u]|) over all V which is O(V+E) since the sum of adjacencies is O(E) (2E for undirected graph and E for a directed one)

Upvotes: 3

trincot
trincot

Reputation: 350262

Your "examples of thought" illustrate that the complexity is not O(V*E), but O(E). True, E can be a large number in comparison with V, but it doesn't matter when you say the complexity is O(E).

When the graph is connected, then you can always say it is O(E). The reason to include V in the time complexity, is to cover for the graphs that have many more vertices than edges (and thus are disconnected): the BFS algorithm will not only have to visit all edges, but also all vertices, including those that have no edges, just to detect that they don't have edges. And so we must say O(V+E).

Upvotes: 7

Azamat Zhurtbayev
Azamat Zhurtbayev

Reputation: 233

Consider a situation when you have a tree, maybe even with cycles, you start search from the root and your target is the last leaf of your tree. In this case you will traverse all the edges before you get into your destination.

E.g.

0 - 1
1 - 2
0 - 2
0 - 3

In this scenario you will check 4 edges before you actually find a node #3.

Upvotes: 0

Related Questions