Time complexity of BFS algorithm if sorting the queue is necessary

user_2023745 0
Viewed 43

In BFS, you typically have something like

while q:
  popped_node = q.popleft()
  res.append(do_work(popped_node))
  for child in popped_node.children:
    q.append(child)
return res

But say for some reason you needed to iterate over the children in order based on some key, so you would have

while q:
  popped_node = q.popleft()
  res.append(do_work(popped_node))
  for child in sorted(popped_node.children, key=lambda x: x._id):
    q.append(child)
return res

Typically the time complexity of BFS is O(N), number of nodes. How does adding this sorting portion affect the time complexity?

breadth-first-search time-complexity
1 Answers

Let's consider there are V vertices in a graph G with E edges. Looking at you code:

// This loop runs V times
while q:
  popped_node = q.popleft()
  res.append(do_work(popped_node)) // assuming this is O(1)

  // this loop runs O(Ei + Eilg(Ei)) times, where Ei is number of edges connected with current vertex
  // Eilg(Ei) is upper bound for sorting algorithm
  for child in sorted(popped_node.children, key=lambda x: x._id):
    q.append(child)
    
  return res

Time complexity is as follows:

= O(1) + O(E1) + O(E1lgE1) + O(1) + O(E2) + O(E2lgE2) + ... O(1) + O(EV) + O(EVlgEV)

= V*(O(1) + Ei) + ∑i=1V O(EilgEi)

= O(V + E) + ∑i=1V O(EilgEi)

This extra term ∑i=1V O(EilgEi) in time complexity is due to sorting.

Assuming there is only single edge b/w any two vertices, in worst case Ei -> V i.e. a fully connected graph
Time complexity can then be given as:
= O(V + E) + ∑i=1V O(EilgEi)

= O(V + E) + ∑i=1VO(VlgV)

= O(V + E) + O(V2lgV)

Two points to mention here:

  • If sorting utilises sorting algorithm other than comparison sort, like counting sort, bucket sort etc. with linear complexity then ∑i=1V O(EilgEi) can be replaced by ∑i=1VO(Ei) = O(E), which evaluates to O(V + E).
  • Although for adjacency matrix this is a good tight bound, but for adjacency list(or sparse graph) this will be a loose upper bound.
user_99289080
Related