What is the complexity of depth first traversal that don't label nodes as discovered?
Question
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);
}
}
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange