we note that the proof tree of 1 is traversed onl once, the tree of 2 is traversed once for each solution generated b . 1, the tree of . 3 once for each solution of l 2 , etc.

onse  uentl  the total cost of proving    uation 1 is

( n) l 2 b ) n b / b   Sols( A;  ) ( i i i) ( ) :l b Sols( A 1 , ...A i -1 )
To compute u uation one must know the cost and the solution set for each subgoal under each binding. To reduce the amount of information needed, we derive an e  uivalent formula, which uses average cost and average number of solutions. Definition:  et   be a set of subgoals,   a subgoal,   efine cost(  )   to be the average cost of over all solutions of and nsols( ) to be its average number of solutions over all solutions of

cost ( ) undefined nsols( undefined
rom the first definition, it follows that

( i i ) cost( i) Ai, Ai-i ( ) ( i 1 ) l b Sols( A1, A1-1 )
If we appl the second definition recursivel , we obtain

$\left(\begin{array}{ccccc}1&i\end{array}\right)$$\sum\limits_{\begin{array}{c}b\ \ \text{Sol}\left(\begin{array}{ccccc}A_{1},...A_{i-1}\end{array}\right)\\ \left(\begin{array}{ccccc}1&i&1\end{array}\right)&n\overline{\text{Sol}}\left(\begin{array}{ccccc}i\end{array}\right)&A_{1},...A_{i-1}\\ \prod\limits_{j=1}^{i}n\overline{\text{Sol}}\left(\begin{array}{ccccc}j\end{array}\right)&A_{1},..A_{j-1}\end{array}$$\left(\begin{array}{ccccc}\end{array}\right)$
Note that we defined thus, these e  uations hold also for 1. Incorporation of utions and into ields uation

2
$$44$$