2
$\begingroup$

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);
    }
}
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Jun 10 '14 at 8:31
  • $\begingroup$ 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.) $\endgroup$ – Raphael Jun 10 '14 at 10:36
  • $\begingroup$ @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. $\endgroup$ – bobbaluba Jun 10 '14 at 10:51
3
$\begingroup$

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$:

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.