In the previous sections, we saw that both belief propagation and variable elimination are inter-related. Belief propagation is an extension of the variable elimination algorithm on clique trees. So, one might think that they would have the same computational complexity. However, in reality, belief propagation has some advantages over variable elimination.

The major advantage is the ability to query over multiple variables of a model with a single computation (that is, calibration of the clique tree). Once the tree is calibrated, we could query about multiple variables without performing any further computation. However, in the case of variable elimination, we have to run the algorithm more than once. Thus, if we have such a problem, in which we need to query the model multiple times, we should definitely use belief propagation.

On the flipside, belief propagation also has a disadvantage over variable elimination. Clique trees are a memory-expensive data structure. Moreover, in belief propagation, we have to store the generated intermediate factors, whereas in the case of variable elimination, we just discard them. Belief propagation is also less flexible as compared to variable elimination, as the clique tree is fixed and predetermined. So, in the case of very huge networks, memory might become a constraint when using belief propagation.

In a nutshell, we can say that variable elimination is computationally expensive, whereas belief propagation is memory expensive. We have to consider the trade-offs to decide which algorithm to go for. If we have a very large network, then variable elimination would be an attractive solution as it wouldn't be expensive in terms of memory. However, in the case of smaller networks and multiple queries, where computational time matters, it would be better to go with the belief propagation approach.