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

Question

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

Grandeur

Answer 1

I will asume that you are refering to AC-3 consistency algorithm. This algorithm is nicely and simply described here. I will be refering to this decsription of the algorithm.

First, lets calculate the complexity of the method REVISE (method revises one arc between two domains). For each value in one domain, it is examining all the values of the second domain. So the complexity of the REVISE method would be d² where d is maximum domain size.

Now, how many times, at worst, will be the REVISE called? Initially, there are all the arcs in the queue. Every time the REVISE is called, one arc is removed from the queue. That would be e calls of the method. But we are also adding arcs back to the queue. How many times can we do that? Well, 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 queue d times.

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

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

Zoosperm

Thanks a lot Fila !! – Grandeur

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

Couldn't a hash set be used to track each variable's domain to remove a factor of d? – Atmolysis