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.

Darwiche&Provan