searchPCwit is O(n + nd) since there are O(n) variables constrained with both xi and xj and, after making the checks in line 3, their domains must be searched for a PC-witness, each time from scratch with cost O(nd). Through the use of LastP C no value of xj will be checked more than once over all the O(d) times xj is extracted from L, meaning that for any value ai ∈ D(xi) and any variable xj , the overall cost of *searchPCwit* will be O(dn + nd2) = O(nd2). Hence, *searchPCsup* will cost O(nd2) for one value of xi, giving O(nd3) for d values. Since, in the worst case, this process will be repeated for every pair of variables xi and xj that are constrained, the total cost of *searchPCsup* will be O(end3). This is the node complexity of lmaxRPC3.

In *checkPCwit* the algorithms iterate over the variables in a triangle with xj and xi. In the worst case, for each such variable xk, D(xj ) will be searched from scratch for a PC-witness of ai and its current PC-support in xk. As xj can be extracted from L O(d) times and each search from scratch costs O(d), the total cost of checking for a PC-witness in D(xj ), including the checks of line 4 in *checkPCwit*, will be O(d + d 2). For d values of xithis will be O(d 3). As this process will be repeated for all triangles of variables, whose number is bounded by en, its total cost will be O(end3). If no PC-witness is found then a new PC-support for aiin D(xk) is seeked through *searchPCwit*. This costs O(nd2) as explained above but it is amortized with the cost incurred by the calls to *searchPCwit* from searchPCsup. Therefore, the cost of *checkPCwit* is O(end3). This is also the node complexity of maxRPC3.

The branch complexity of (l)maxRPC3 is also O(end3). This is because the use of **LastP C** ensures that for any constraint ci,j and a value ai ∈ D(xi), each value of xj will be checked at most once for PC-support while going down the branch. Therefore, the cost of **searchP Cwit** is amortized.

Proposition 4 The node and branch time complexities of lmaxRPC3rm and maxRPC3rm are O(end4) and O(en2d 4) respectively.

Proof: The proof is similar to that of Proposition 3. The main difference with lmaxRPC3 is that since **lastP C** is not updated incrementally, each time we seek a PC-support for a value ai ∈ D(xi) in xj , D(xj ) will be searched from scratch in the worst case. This incurs an extra O(d) cost to *searchPCsup* and *searchPCwit*.

Hence, the node complexity of lmaxRPC3rm is O(end4). Also, the total cost of searchPCwit in one node cannot be amortized. This means that the cost of *searchPCwit* within *checkPCwit* is O(nd2). Hence, the node complexity of maxRPC3rm is O(en2d 4). The branch complexities are the same because the calls to *searchPCwit* are amortized.