[Solved]: What is the complexity of depth first traversal that don't label nodes as discovered?

Problem Detail: 

I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before.

  A  / \ B   C  \ /   D   |   E 

If run on this graph, the algorithm will traverse in this order:

A, B, D, E, D, B, A, C, D, E

Is there any way I can express the run-time complexity of this algorithm in terms of edges, nodes, or the depth of the graph? I expect it would be high, I have the feeling it will be exponential, but I'm struggling to explain why.

EDIT: The real algorithm that I am analyzing is computing the result of an expression tree, only it is not run at a tree, but at a DAG. This means, that nodes that have several parents get computed once for all parents.

Simple pseudo-code for the algorithm might be:

calculate(root){     if(root.isLeaf){         return root.value;     } else {         leftval = calculate(root.left);         rightval = calculate(root.right);         return root.operator(leftval, rightval);     } } 

Asked By : bobbaluba

Answered By : Rick Decker

For general DAGs, the runtime could indeed be exponential in the depth. Here's an example of a family of such graphs. Let $G_d$ be a digraph comprised of a vertex stacked on a collection of 4-cycles as below, where I've illustrated $G_3$:

In this figure, the edges are directed from top to bottom and every vertex has two children. The number of function calls your algorithm makes (and hence the run time) for a digraph $G_d$ of depth $d$ will satisfy $T(0)=1, T(d)=2T(d-1)+1$, since every $G_d$ is comprised of a root vertex at the top with two overlapping copies of $G_{d-1}$ below it. This recurrence has solution $T(d) = 2^{d+1}-1$, exponential in the depth.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27564

 Ask a Question

 Download Related Notes/Documents