Proof:
Let
. By definition of ,
therefore a partitioning of is
as shown in Figure 3.7. According to the definition of :
Thus, using the partitioning of :
=  
+  
+  
=  
+  
+ 
When injecting the definition of in the last line, the equation becomes:
The computation method for we have presented requires the knowledge of the metrics and , and computations of Least Common Ancestors. Each of the metrics and can be computed for all links of prior to any evaluation of (lines 1 to 3 in Algorithm 1) with the following recursive relations:
In [33] the authors show that it is possible to determine a Least Common Ancestor for any pair of nodes in a tree in constant time after a linear preprocessing of . This tree preprocessing is performed in line 4 of Algorithm 1.
Consider Algorithm 1. In lines 1 to 3, the metrics and are computed for every link of . Computing each metric for all links of the tree can be performed in linear time with the recursive formula given in Section 3.3.1. Therefore, the time complexity of lines 1 to 3 is .
In line 4, tree is preprocessed so as to speed up further LCA computations. After the tree preprocessing, it is possible to determine the LCA of any pair of nodes in constant time. A linear tree preprocessing algorithm is proposed in [33], hence a time complexity of for line 4.
Nodes and are determined in lines 5 to 8 by computing the metric between a leaf and another node. Thus, metrics have to be computed and compared. Computing with Definition 3 involves the addition of products between link failure rate weights and metrics for all links of the tree except on the path between two nodes, hence a complexity of . The complexity of lines 5 to 8 is thus if is computed with its definition. If is computed with the expression from Equation 3.2, then three terms must be added. Term (1) involves to determine the LCA of a pair of nodes and the addition of metrics for links downstream of vertices of the protected path between the two nodes for which is computed. Determining a LCA is performed in constant time as already stated and at most all metrics are added in Term (1), hence a time complexity of to compute Term (1) of Equation 3.2. Term (2) involves the addition of products between and metrics for all links on the path between and root . Since a path can be up to links long, the time complexity for computing Term (2) of Equation 3.2 is . Same as Term (1), Term (3) requires the addition of up to terms hence a time complexity of . In summary, computing a single metric between two leaves can be done in time with either the definition or the method previously introduced, and the time complexity of lines 5 to 8 is also in the general case.
Last, line 9 computes a backup path between two vertices in a graph of edges. Classic Dijkstra's shortest path algorithm [24] solves this problem in time .
Overall, the time complexity of Algorithm 1 is:
Now consider Algorithm 2. Lines 1 to 7 of Algorithms 1 and 2 are identical. In line 8, metric is determined for
nodes, then the set of all these metrics is sorted. Since computing a metric takes time and sorting a set of size takes time
, the time complexity of line 8 of Algorithm 2 is
. In lines 9 to 13, a shortest path is computed for up to pairs of nodes, thus the time complexity of lines 9 to 13 is
. Overall the time complexity of Algorithm 2 is:
Finally, consider Algorithm 3. The maximum length for a path in a tree of nodes is thus the time complexity of lines 1 to 3 is . In lines 4 to 6, metrics are updated. Updating a single metric has a time complexity of hence a time complexity of for lines 4 to 6. In line 7, the minimum of a set of is determined in time and in line 8 a shortest path is computed in time
. Therefore, the complexity of Algorithm 3 is:
In the next sections, we show that the time complexity of Algorithm 1 in the average case is and give a worst case example where the upper bound is reached. We present similar results for Algorithms 2 and 3.
First, consider Algorithm 1. The computations performed in lines 1 to 4 are the same as in the general case, hence a complexity of . In lines 5 to 8, metric must be computed between each of the leaves and all other nodes. Therefore metrics must be computed. Suppose we use the definition to compute . Computing involves the addition of products between and metrics for all links of the tree except those on the protected path between and another leaf. Therefore, products have to be added hence a time complexity of to compute each of the metrics , and a complexity of for lines 5 to 8 of Algorithm 1. This is the same result as in the general case.
Now suppose that we use the method presented in Section 3.3.1 to compute between two nodes and of . First, part (1) of Equation 3.2 requires the addition of at most terms for each vertex on the protected path for which is computed. A protected path consists of at most vertices, thus complexity of Term (1) is . Second, the number of links on the path from to is at most . Determining an LCA is done in constant time as previously stated therefore part (2) of Equation 3.2 has a complexity of . Third, Term (3) involves the addition of at most metrics for each link of the path between and , hence a time complexity of for Term (3) of Equation 3.2. Overall, the time complexity of the computation of all metrics performed by lines 5 to 8 of Algorithm 1 is , instead of if the definition of was used.
The last step of Algorithm 1 computes a shortest path between two nodes in a graph with edges. The classic Dijkstra's shortest path Algorithm [24] solves the problem in time .
All in all, the complexity of Algorithm 1 is:
Now consider Algorithm 2. We have shown above that the time complexity of lines 1 to 7 is . Computing and sorting the set of all metrics in line 8 takes time
. Computing all possible backup paths takes time
, hence the time complexity of Algorithm 2 in the general case:
Last, consider Algorithm 3. The length of the path between and is thus computing metrics in lines 1 to 3 is done in time . The size of the set
is therefore updating a metric takes time . Updating all the metrics takes time
(lines 4 to 6). In line 7, determining a minimum of values takes time . In line 8, a shortest path is computed in time
. The time complexity of Algorithm 3 in the average case is:
All three Algorithms 1, 2 and 3 are faster in the average case than in the general case. In the next section, we determine the worst case for each algorithm.

Consider Algorithm 1. The general expression for its time complexity is . The upper bound can be reached only when and . Consider the graph and the tree depicted in Figure 3.8. Suppose that all links from the tree have the same relative failure probability and the same weight . Tree has links and leaves.
Lines 1 to 4 take time to complete. Then, metrics must be computed to determine and . Computing each metric takes time . Indeed, in this case the protected path between a leaf and any node is reduced to . Term (1) of Equation 3.2 is the sum of the metrics for all links of the tree except the two links of the protected path, hence a complexity for Term (1). Since , Terms (2) and (3) of Equation 3.2 are equal to zero. In this case, using the alternate method to compute each metric is as complex as using the definition of . Complexity of lines 5 to 8 is . Determining the shortest path in this graph is performed in time .
In summary, in this case the complexity of Algorithm 1 is . We have shown that was an upper bound for the complexity of Algorithm 1, and presented a case where this bound was attained.

We now show that the upper bound can be attained for Algorithm 2. The general expression of the time complexity is . Consider the network and the tree depicted in Figure 3.9. The tree is disconnected from the other nodes of the network and therefore Algorithm 2 computes a backup path between all possible pairs of nodes of the tree before failing to find a backup path. Since , the time complexity of Algorithm 2 in this particular case is .

Last, we show that the upper bound can be attained for Algorithm 3. Consider Figure 3.10 where node leaves the group. The path between and is such that and is located in the middle of this path. After leaves the group we have and . Then, metrics must be recomputed. The path between and has links thus for any two nodes and such that the size of the set is . There are such pairs of nodes. According to Equation 3.1, updating one metric takes time . Therefore, updating all metrics takes time . In this case, the time complexity of Algorithm 3 is .