The search space for both TO and UA can be characterized as a tree of plans. The root node in the tree corresponds to the top-level invocation of the algorithm, and the remaining nodes each correspond to a recursive invocation of the algorithm. Note that in generating a plan, the algorithms make both operator and ordering choices, and each different set of choices corresponds to a single branch in the search tree.
We denote the search tree for TO by 
and,
similarly, the search tree for UA by 
. The number
of plans in a search tree is equal to the number of times the planning
procedure (UA or TO) would be invoked in an exhaustive
exploration of the search space. Note that every plan in
and is unique, since each step in a plan
is given a unique label. Thus, although two plans in the same tree
might both be instances of a particular operator sequence, such as 
, the plans are distinct because their steps have
different labels. (We have defined our plans this way to make our
proofs more concise.)
We can show that for any given problem, is at least as large
as , that is, the number of plans in is greater
than or equal to the number of plans in . This is done by
proving the existence of a function 
which maps plans in
into sets of plans in that satisfies the
following two conditions.
, there exists a non-empty set 
of plans in such that 
.
maps distinct plans in to disjoint sets of
plans in ; that is, if 
and 
, then 
.
Let us examine why the existence of an with these two
properties is sufficient to prove that the size of UA's search
tree is no greater than that of TO. Figure 5
provides a guide for the following discussion. Intuitively, we can
use to count plans in the two search trees. For each plan
counted in , we use to count a non-empty set of
plans in . The totality property means that every time
we count a plan in , we count at least one plan in
; this implies that 
. Of course,
we must further show that each plan counted in is
counted only once; this is guaranteed by the disjointness property,
which implies that 
. Thus, the conjunction of
the two properties implies that 
.
We can define a function that has these two properties as
follows. Let U be a plan in , let T be a
plan in , and let parent be a function from a plan
to its parent plan in the tree. Then 
if and only
if (i) T is a linearization of U and (ii)
either U and T are both root nodes of their respective
search trees or 
. Intuitively,
maps a plan U in to all linearizations which
share common derivation ancestry.
This is illustrated in
Figure 5, where for each plan in a dashed
line is drawn to the corresponding set of plans in .
We can show that satisfies the totality and disjointness
properties by induction on the depth of the search trees. Detailed
proofs are in the appendix. To prove the first property, we show that
for every plan contained in , all linearizations of that
plan are contained in . To prove the second property, we
note that any two plans at different depths in have
disjoint sets of linearizations, and then show by induction that any
two plans at the same depth in also have this property.
How much smaller is than ? The mapping
described above provides an answer. For each plan U in
there are 
distinct plans in
TO, where is the number of
linearizations of U. The exact number depends on how unordered U
is. A totally unordered plan has a factorial number of linearizations
and a totally ordered plan has only a single linearization. Thus, the
only time that the size of equals the size of
is when every plan in is totally
ordered; otherwise, is strictly smaller than
and possibly exponentially smaller.
