Time complexity of AC-3 algorithm

Question

This is the AC-3 algorithm's (pseudo) code:

function AC-3(csp) returns false if an inconsistency is found and true otherwise
    queue ← a queue of arcs, initially all the arcs in csp
    while queue is not empty do
        (Xi ,Xj ) ← Pop(queue)
        if Revise(csp,Xi ,Xj ) then
            if size of Di = 0 then return false
            for each Xk in Xi .Neighbors− {Xj } do
                add (Xk,Xi) to queue
    return true

function Revise(csp,Xi ,Xj ) returns true iff we revise the domain of Xi
    revised ← f alse
    for each x in Di do
        if no value y in Dj allows (x, y) to satisfy the constraint between Xi and Xj then
            delete x from Di
            revised ← true
    return revised

I'm studying on the book Artificial Intelligence - A Modern Approach (4th edition) and this is what it says regarding this algorithm's time complexity:

Assume a CSP with n variables, each with domain size at most d, and with binary constraints (arcs). Each arc (Xi, Xj) can be inserted in the queue only d times because X_i has at most d values to delete. Checking consistency of an arc can be done in O(d^2) time, so we get O(cd^3) total worst-case time.

• I understand that each arc (Xi, Xj) can be inserted in the queue only d times (because Xi has at most d values to delete, and they can be deleted one by one in the worst case).
• I don't understand how checking consistency of a single arc can be done in O(d^2). What I thought it could have been was O(cd) instead, since in the worst case it can delete one by one all the values from all the variables' domains.
• I don't understand the total worst-case time it gives, which is O(cd^3). In this case, it would have seemed to me that it could instead have been O(cd^2).

How would you go about calculating the time complexity of this algorithm? Where was I wrong?

Thank you.

Answer 1

I don't understand how checking consistency of a single arc can be done in O(d^2).

If we look at the REVISE function in the AC-3 algorithm, it says:

for each value x in Di:
   if no value y in Dj allows ...

We execute the for loop in the 1st line above d times and the 2nd line also d times in worst case if we had to search every value in Dj to find a satisfying assignment (x, y) for the constraint (or to determine no satisfying assignment possible).

So that makes O(d^2) to check each arc using AC-3.