The worst-case complexity of running the AC-3 algorithm on a tree-structured constraint satisfaction problem is . On a tree-structured graph there is no arc that will be considered more than once.

The worst-case complexity of AC-3 algorithm is

Here, E is the number of edges and D is the size of the largest domain.