Why is the complexity of Arc-Consistency Algorithm O(cd^3)?

Question

Why is the complexity of Arc-Consistency Algorithm O(cd3)?

Answer 1

Many times, this is also written as O(n^2 d^3), to talk in terms of n, instead of e. 

First, let us calculate the complexity of the method REVISE (method revises one arc between two domains). For each value in one domain, it is studying all the values of the second domain. So the complexity of the REVISE method will be square of d where d is the maximum size of the domain.

Now, for the worst case of function REVISE, originally there are all the arcs in the queue. Every time the REVISE is called, one arc is removed from the queue. That would be an e number of calls of the method. But the arcs are also added back to the queue. We are adding arc back to the queue only if a value was deleted from the domain the arc is pointing to. One arc is pointing to one domain, so we can only add it as many times as the number of values in that domain. So at worst, we are adding every arc back to the queued times.

REVISE is called at maximum e + ed times where e is the number of arcs.

When we put it all together, we find out that the complexity of the whole algorithm is O((e+ed)d2) which is O(ed3).

You can refer to the following link for the better understanding of the algorithm of AC-3 consistency: http://ktiml.mff.cuni.cz/~bartak/podminky/lectures/CSP-lecture04eng.pdf