0

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.

In this case, we have DFS going through Paths:

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

The computational complexity was 6 because it takes 3 iterations in the first path, 2 in the second, 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?

time-complexitybig-ocomplexity-theorydepth-first-searchdirected-acyclic-graphs