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

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);
}
}

• Problems have complexities, algorithms have costs. That aside, have you tried constructing a worst-case instance? Can you put into words what the algorithm does? – Raphael Jun 10 '14 at 8:31
• Regarding your pseudo code, I guess calculate and calculate_expression mean the same thing? Now it is no longer clear what the question is: are you asking about the runtime on arbitrary DAGs, or about the runtime on such DAGs that are the result of minimising an arithmetic expression? (The answers may differ.) – Raphael Jun 10 '14 at 10:36
• @Raphael: Yes, you are right, edited the pseudo code. Regarding your other question, the DAG is not built from a textual expression like "1+2*1", but by creating nodes and edges. So, yes, I guess it's an arbitrary DAG. – bobbaluba Jun 10 '14 at 10:51

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7263665795326233, "perplexity": 586.7895362862338}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-34/segments/1596439738960.69/warc/CC-MAIN-20200813043927-20200813073927-00199.warc.gz"}