Search code examples
time-complexitybig-ocomplexity-theorydepth-first-searchdirected-acyclic-graphs

Computational complexity of DFS over the worst case DAG

I got confused by calculating the worst-case DAG complexity when you do a Naive DFS from one node to another node.

For example in the following DAG, Node A act as a start node, and if we always pick the last node, in this case, Node D as the end node, use DFS to calculate all path from A to D.

enter image description here

In this case, we have DFS going through Paths:

path 1st:  A -> B -> C -> D
path 2nd:  A -> B -> D
path 3rd:  A -> C -> D
path 4th:  A -> D

The computational complexity was 8 because it takes 3 iterations in the first path, 2 in the second, 2 in the third, and 1 in the last one.

Now if we expand this graph, add more nodes after.

Assuming we have N nodes, what is O(N) then?

The way I do the calculation for the number of total paths is like, every time we add a new node to an N-node-DAG, to replace Node A as the new beginning node, we add N new edge here. Because we need to add edges to go from the new start node to all nodes that existed.

If we assume P as total paths, we have
P(N) = P(N-1) + P(N-2) + P(N-3) + .... + P(1)

then you have 
P(N) = 2 * P(N-1)

then
P(N) = O(2^N)

However, if we consider that not all paths is using the computational complexity of O(1), for example, the longest path that goes through all the nodes, we take O(N) for that single path, the actual cost is higher than O(2^N).

So what could that be then?

Solution

  • I think I found out.

    so if we consider that each new node will add a new edge from the new node to each node in DAG, traversing each of those new edges will take complexity as 1.

    Then we could have (if we use C as computational complexity):

    C(N) = 1 + C(N-1) + 1 + C(N-2) + 1+ C(N-3) + .... + 1 + C(1)

then you have 

C(N) = 2 * C(N-1) + N - 1
     = 2^2 * C(N-2) + 2 * (N-2) + N - 1
     = 2^3 * C(N-3) + 2^2 * (N-3) + 2 * (N -2) + N - 1
     = 2^(N-1) * C(1) + 2^(N-2) * 1 + ...... + N - 1

    At this moment this becomes a sum of the geometric progression of N, the ratio is 2, so the highest rank item is at 2^N.

    Thus O(2^N) is the answer.