0
$\begingroup$

CLRS pseudocode:

begin
   for each vertex u in G.V - {s}, do
      u.color := white
      u.d := infinity
      u.p := NIL
   done
   s.color := green
   s.d := 0
   s.p := NIL
   Q := NULL
   insert s into Q
   while Q is not null, do
      u = delete from Q
      for each v in adjacent to u, do
         if v.color = white
            v.color := green
            v.d := u.d + 1
            v.p := u
            insert v into Q
         end if
      done
      u.color = dark_green
   done
end`

In the clrs it says that the insertion and deletion operations with the queue require an O (1) time, so the total time of operations with the queue is O (V). (V because each vertex is visited at least once). instead the time to inspect the adjacency list of each node is O (E). Then we have another O (V) for initialization. So the total time is O (V + E) which in the worst case becomes O (V ^ 2), this depends on whether the graph is dense or not.

Now my question is: Since we have two cycles nested the complexity shouldn't be O (V * E), I can't understand why a sum operation is performed instead of multiplying.

$\endgroup$
2
  • $\begingroup$ Imaging node $i$ has out-degree $d_i$ (the number of neighbors). Now you'll agree that since every node is visited only once we have for both loops combined: $\sum_{i=1}^{n} (1 + d_i)$ ($1$ is just the constant cost, $d_i$ the cost of the inner loop). So what does $\sum_{i = 1}^n d_i$ evaluate to? $\endgroup$
    – plshelp
    Oct 9, 2022 at 18:12
  • $\begingroup$ di should evaluate all edges so it should cost O (E) with E varying between 1 and V ^ 2 depending on the density of the graph. (perhaps on the summation you should use V instead of n.) $\endgroup$
    – mimmolg99
    Oct 9, 2022 at 18:56

1 Answer 1

1
$\begingroup$

I will suppose here that the graph is undirected, but the same reasonning can be done with a digraph.

Using an implemention of a graph as an array of adjacency lists, the adjacency list of any vertex $v$ is its number of neighbors, $\deg(v)$.

The BFS inspects each adjacency list at most once during the graph traversal (and exactly once if the graph is connected). That means that the total complexity is: $$\mathcal{O}\left(\sum\limits_{v\in V}(\deg(v) + 1)\right)$$ Here, the $+1$ is necessary, as inspecting an adjacency list costs $\mathcal{O}(1)$ time, even if the list is empty. Now, a very useful formula for complexity on graphs is: $$\sum\limits_{v\in V}\deg(v) = 2|E|$$ It can be proven quite easily when noting that each edge increases the sum of degrees by two (one for each extremity).

Finaly, we conclude that the complexity is: $$\mathcal{O}\left(\sum\limits_{v\in V}(\deg(v) + 1)\right) = \mathcal{O}(2|E| + |V|) = \mathcal{O}(|E| + |V|)$$

$\endgroup$
6
  • $\begingroup$ all very clear thanks for the explanation $\endgroup$
    – mimmolg99
    Oct 9, 2022 at 19:41
  • $\begingroup$ @mimmolg99 If you want to be more precise, the complexity is $\mathcal{O}(|E_C| + |V|)$, where $E_C$ is the set of edges of the connected component $C$ of the vertex $s$. $\endgroup$
    – Nathaniel
    Oct 9, 2022 at 19:46
  • $\begingroup$ it is correct to say that in the best case then the complexity will be O (V) in the worst case it will be O (V ^ 2) and in the average case O (E + V). In the best case I think it is O (V) because E should be 1 while in the worst case it should be V ^ 2. what do you think? $\endgroup$
    – mimmolg99
    Oct 9, 2022 at 19:52
  • $\begingroup$ While it is true that the best case is $\mathcal{O}(|V|)$ and the worst case is $\Theta(|V|^2)$, you can't really say that the average case is $\mathcal{O}(|E| + |V|)$ because 1) it is always $\mathcal{O}(|E| + |V|)$. 2) average complexity implies that you consider a certain random distribution of graphs (and with the uniform distribution over all graphs with $|V|$ vertices, the average number of edges is $\Theta(|V|^2)$). $\endgroup$
    – Nathaniel
    Oct 9, 2022 at 20:01
  • $\begingroup$ I understand.. thanks 🙏 $\endgroup$
    – mimmolg99
    Oct 9, 2022 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.