2

I am trying to understand how/why complexity of DFS is O(V+E). Here is my attempt at analysing complexity of pseudo-code iterative DFS.

DFS(G, t)
{

1   stack S = new empty Stack of size G.|V|  ... O(1)
2   S.push(t)                                ... O(1)

3   while(S is not Empty)                    ... O(|V|), this will always be =<|V|
    {
4       u = S.pop()                          ... O(1)

5       if(u.visited = false)                ... O(1)
        {
6            u.visited = true                ... O(1)

7            for-each edge (u,v) in G.E      ... O(|E|), this will always be =<|E|
8                if(v.visited = false)       ... O(1)
9                    S.push(v)               ... O(1)
        }
    }
}

Now combining complexity of each line we have:

O(1) + O(1) + O(|V|)[O(1) + O(1) + O(1) + O(E)[O(1) + O(1)]] = O(2) + O(V) + O(V) + O(V) + O(V) + O(V * E) + O(V * E) = 4*O(V) + 2*O(V * E) = O(V * E)

I did not get O(V+E)? Can anyone show me mathematically how we achieve O(V+E)?

Can anyone provide insight?

lucidgold
  • 4,432
  • 5
  • 31
  • 51

1 Answers1

8

Let's make this simple.

The outer loop, it only loops over S once, removing each element it sees. Thus O(|V|) in your notation.

The inner loop, it only loops over your edges once, removing each element it sees. Thus O(|E|) in your notation.

However it's not for each element of S you remove every edge. You remove all nodes and all edges, thus O(|V|+|E|).

It should however be noted that the above is only true in intent. Your implementation is relatively terrible, and it's actually O(|V|*|E|) because you don't remove the edges from the list, you only mark the nodes as visited. Same effect at the end, but you still loop over every single edge for every single node.

Blindy
  • 65,249
  • 10
  • 91
  • 131
  • As a side note, you should probably avoid writing operations like that "sum" for the big-O notation. Those things aren't numbers or anything like that, they're sets of functions. There's no `+` defined for sets of functions. And the way you implied that `O(1)+O(1)=O(2)` should raise the hairs on your back if you understood what it actually means. – Blindy Nov 12 '15 at 05:42
  • I thought I was removing the edges on line 4 – lucidgold Nov 12 '15 at 06:21
  • `S` is the list of nodes, not of edges. You're removing the nodes only. – Blindy Nov 12 '15 at 06:48