The computational complexity of the algorithm for generating Q-DAGs is
determined by the computational complexity of the clustering algorithm.
In particular, the proposed algorithm applies a 
-operation
precisely when the clustering algorithm applies an addition-operation.
Similarly, it applies a 
-operation
precisely when the clustering algorithm applies a multiplication-operation.
Therefore, if we assume that and take
constant time, then both algorithms have the same time complexity.
Each application of or ends up adding
a new node to the Q-DAG. And this is the only way a new node can be added
to the Q-DAG. Moreover, the number of parents of each added node is equal
to the number of arguments that the corresponding arithmetic operation
is invoked on in the clustering algorithm. Therefore, the space complexity
of a Q-DAG is the same as the time complexity of the clustering algorithm.
In particular, this means that the space complexity of Q-DAGs in terms of the number
of evidence variables is the same as the time complexity of the clustering
algorithm in those terms. Moreover, each evidence variable 
will
add only 
evidence-specific nodes to the Q-DAG, where is the number of
values that variable can take.
This is important to stress because without this complexity guarantee
it may be hard to distinguish between the proposed approach and a
brute-force approach that builds a big table containing all possible
instantiations of evidence variables together with their corresponding
distributions of query variables.