The worst-case running time of the routine to initialize the MUSE AC-1
data structures (in Figure 22) is O 
, where n is the number of nodes in a MUSE CSP and l is
the number of labels. Given that the number of (i,j) elements in
E is O 
and the domain size is O(l), the size of the
Counter and S arrays is O 
. To determine the number of
supporters for a given arc-label pair requires O(l) work; hence,
initializing the Counter and S arrays requires O 
time.
However, there are O Prev-Support and Next-Support sets,
where each Prev-Support[(i,j),a] and Next-Support[(i,j),a]
requires O(n) time to compute, so the time to calculate all
Prev-Support and Next-Support sets is O 
. Finally, the time
needed to calculate all Local-Next-Support and Local-Prev-Support sets
is O because there are O(nl) sets with up to O(n)
elements per set.
The worst-case running time for the algorithm which prunes labels that are not MUSE
arc consistent (in Figures 23 and 24) also operates
in O time.
Clearly the Counter array contains O entries (a similar argument
can be made for the S array)
to keep track of in the
algorithm. Each Counter[(i,j),a] can be at most l in magnitude, and it can
never become negative, so the maximum running time for line 4 in
Figure 23
(given that elements appear on List only once because of M)
is O . Because there are O Next-Support
and Prev-Support lists, each up to O(n) in size, the maximum running time
required for lines 3 and 9 in Figure 24 is O . Finally, since there are
O(nl) Local-Prev-Support and Local-Next-Support sets from which to eliminate
O(n) elements, the maximum running time of lines 14
and 23 in Figure 24 is
O . Hence, the maximum running time of the MUSE CSP arc consistency
algorithm is O .
The space complexity of MUSE CSP AC-1 is also O
because the arrays Counter and M contain O elements, and
there are O S sets, each containing O(l) items;
O Prev-Support and Next-Support sets, each containing O(n) items; and
O(nl) Local-Next-Support and Local-Prev-Support sets, each containing
O(n) items.
By comparison, the worst-case running time and space complexity for CSP arc consistency is
O , assuming that there are 
constraint arcs.
Note that for applications where l=n,
the worst-case running times of the algorithms are the same order (this is true for
parsing spoken language with a MUSE CSP). Also, if 
is
representable as planar DAG (in terms of Prev-Edge and Next-Edge, not E), then
the running times of the two algorithms are the same order because the average
number of values in Prev-Support and Next-Support would be a constant.
On the other hand, if we compare MUSE CSP to the use of multiple CSPs for problems where
there are k alternative variables for a particular variable in a
CSP, then MUSE CSP AC-1 is asymptotically more attractive,
as shown in Table 1.
Table 1: Comparison of the space and time complexity for MUSE arc consistency
on a MUSE CSP to arc consistency on multiple CSPs representing a
node splitting problem (e.g., lexical ambiguity in parsing).