While the size of UA's search tree is possibly exponentially smaller than that of TO, it does not follow that UA is necessarily more efficient. Efficiency is determined by two factors: the time cost per plan in the search tree (discussed in this section) and the size of the subtree explored during the search process (discussed in the next section).
Table 1: Cost per plan comparisons
In this section we show that while UA can indeed take more time
per plan, the extra time is relatively small and grows only
polynomially with the number of steps in the plan,
which we denote
by n. In comparing the relative efficiency of UA and TO, we first consider the number of times that each algorithm step
is executed per plan in the search tree and we then consider the time
complexity of each step.
As noted in the preceding sections, each node in the search tree
corresponds to a plan, and each invocation of the planning procedure
for both UA and TO corresponds to an attempt to extend
that plan. Thus, for both UA and TO, it is clear that the
termination check and goal selection (Steps 1 and 2) are each executed
once per plan. Analyzing the number of times that the remaining steps
are executed might seem more complicated, since each of these steps is
executed many times at an internal node and not at all at a leaf.
However, the analysis is actually quite simple since we can amortize
the number of executions of each step over the number of plans
produced. Notice that Step 6 is executed once for each plan that is
generated (i.e., once for each node other than the root node).
This gives us a bound on the number of times that Steps 3, 4, and 5
are executed. More specifically, for both algorithms, Step 3 is
executed fewer times than Step 6, and Steps 4 and 5 are executed
exactly the same number of times that Step 6 is executed, that is,
once for each plan that is generated. Consequently, for both
algorithms, no step is executed more than once per plan, as summarized
in Table 1. In other words, the number of times each
step is executed during the planning process is bounded by the size of
the search tree.
In examining the costs for each step, we first note that for both algorithms, Step 1, the termination check, can be accomplished in O(1) time. Step 2, goal selection, can also be accomplished in O(1) time; for example, assuming the goals are stored in a list, the select-goal function can simply return the first member of the list. Each execution of Step 3, operator selection, also only requires O(1) time; if we assume the operators are indexed by their effects, all that is required is to ``pop'' the list of relevant operators on each execution.
Steps 4 and 5 are less expensive for TO than for UA. Step 4 of TO
is accomplished by inserting the new operator, 
, somewhere
between 
and 
. If the possible insertion points are
considered starting at and working towards , then
each execution of Step 4 can be accomplished in constant time, since
each insertion constitutes one execution of the step. In contrast,
Step 4 in UA involves carrying out interaction detection and
elimination in order to produce a new plan 
. This step can be
accomplished in O(e) time, where e is the number of edges in the
graph required to represent the partially ordered plan. (In the worst
case, there may be 
edges in the plan, and in the best case,
O(n) edges.) The following is the description of UA's ordering
step, from Figure 3, with some additional implementation
details:
after and before .
Label all steps preceding and all steps
following .
Let 
be the unlabeled steps that
interact with .
Let be the last deleter of 
.
Repeat until is empty:
= Pop()
is still unlabeled then either:
before , and
label and the unlabeled steps before ; or
after , and
label and the unlabeled steps after .
be the resulting plan.
The ordering process begins with a preprocessing stage. First, all
steps preceding or following are labeled as such. The
labeling process is implemented by a depth-first traversal of the plan
graph, starting with as the root, which first follows the
edges in one direction and then follows edges in the other direction.
This requires at most O(e) time. After the labeling process is
complete, only steps that are unordered with respect to are
unlabeled, and thus the interacting steps (which must be unordered
with respect to ) are identifiable in O(n) time. The last
deleter is identifiable in O(e) time.
After the preprocessing stage, the procedure orders each interacting
step with respect to , updating the labels after each
iteration. Since each edge in the graph need be traversed no more
than once, the entire ordering process takes at most O(e) time
(as described in (Minton
et al.,1991b). To see this, note that
the process of labeling the steps before (or after) can stop
as soon as a labeled step is encountered.
Having shown that Step 4 of TO has O(1) complexity and Step 4 of UA has O(e) complexity, we now consider Step 5 of both algorithms, updating the goal set. TO accomplishes this by iterating through the steps in the plan, from the head to the tail, which requires O(n) time. UA accomplishes this in a similar manner, but it requires O(e) time to traverse the graph. (Alternatively, UA can use the same procedure as TO, provided an O(e) topological sort is first done to linearize the plan.)
To summarize our complexity analysis, the use of a partial order means that UA incurs greater cost for operator ordering (Step 4) and for updating the goal set (Step 5). Overall, UA requires O(e) time per plan, while TO only requires O(n) time per plan. Since a totally ordered plan requires a representation of size O(n), and a partially ordered graph requires a representation of size O(e), designing procedures with lower costs would be possible only if the entire plan graph did not need to be examined in the worst case.