Search code examples
algorithmtime-complexitygraph-theorybreadth-first-search

Why is the time complexity of both DFS and BFS O( V + E )

The basic algorithm for BFS:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

So I would think the time complexity would be: 

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

where v is vertex 1 to n

Firstly, is what I've said correct? Secondly, how is this O(N + E), and intuition as to why would be really nice. Thanks

Solution

  • Your sum

    v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

    can be rewritten as

    (v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

    and the first group is O(N) while the other is O(E).