# Optimal Algorithms for Sorting Permutations with Brooms
## 5 Analysis of Algorithm \(D^{*}\) on Millipede Tree
### Analysis and Results  
It is observed that \(D^{*}\) would yield a tighter upper bound than \(D^{\prime}\) for a millipede tree. In the first iteration of \(D^{*}\) on \(M_{k}\), the set \(S\) contains all the leaf nodes and results in two clusters--\(C_{1}\) and \(C_{2}\). \(C_{1}\) and \(C_{4}\) are of same size which contain the leaf nodes in the upper and lower millipede trees respectively (refer Figure 7). The terminal nodes in the path graph \(p_{(k+1)/2}\) are not part of any cluster. Note that, deleting \(C_{1}\) or \(C_{2}\) will result in isomorphic trees (refer Figure 8). Since the size of the largest cluster \(C^{*}\) (\(C_{1}\) or \(C_{2}\)) is less than half of the size of \(S\), only \(|C^{*}|\) markers need to be homed in \(diam(T)\) cost and the remaining markers in the set \(S\) can be homed at a cost of \((diam(T)-1/2)\). This results in two steps \(x_{1}\) and \(x_{2}\) for calculating the total cost in the iteration:  
\(\mathbf{x_{1}}:\delta^{*}=diam(T)*|C^{*}|\)  
```
1:\(\delta^{*}\gets 0\)
2:if\(T\) is a star then
3:\(\delta^{*}\leftarrow\delta^{*}+\lfloor 3/2(|V_{T}|-1)\rfloor\) and terminate. 4:endif
5: Identify \(S\), the set of vertices with maximum eccentricity. 6: Compute clusters for \(S\). 7: Identify \(C=S-C^{*}\) where \(|C^{*}|\) is the max. If there are multiple such clusters, choose the one with minimum distance sum. 8:Case I: \(|C^{*}|\geq|S|/2\)
9:\(\delta^{*}\leftarrow\delta^{*}+|C|*diam(T)\)\(T\gets T\setminus V_{\text{C}}\)
10:End Case 1
11:Case 2: \(|C^{*}|<|S|/2\)\(/|C|\geq|C^{*}|\)
12:\(\delta^{*}\leftarrow\delta^{*}+|C^{*}|*diam(T)\);\(T\gets T\setminus V_{\text{C}}\)
13:if\(|C|-|C*|\) is even then
14:\(\delta^{*}\leftarrow\delta^{*}+(|C|-|C^{*}|)*(diam(T)-1/2)\);
15:else
16:\(\delta^{*}\leftarrow\delta^{*}+(|C|-|C^{*}|)*(diam(T)-1/2)-1/2\);
17:endif
18:End Case 2
19:if\(T\) is not a star graph then go to step 5. 20:else
21:\(\delta^{*}\leftarrow\delta^{*}+\lfloor 3/2(|V_{T}|-1)\rfloor\) and terminate. 22:endif
```  
**Algorithm 1** Algorithm \(D^{*}\)[29]  
In the case of \(D^{\prime}\), there is only one step and all the markers of \(C\) are homed in \(diam(T)\) cost. Two nodes are homed in Step \(x_{2}\) resulting in an improvement of \(1\) in \(\delta^{*}\). As \(D^{*}\) and \(D^{\prime}\) delete all the vertices of \(S\setminus C^{*}\), the resultant tree after the first iteration is same for both. Similarly, every odd iteration generate two clusters and result in an improvement of \(1\). The second iteration generates two clusters \(C_{1}\) and \(C_{2}\), which contain the leaf nodes of the upper and lower millipede trees respectively. Even iterations do not result in any improvement in \(\delta^{*}\), as both the algorithms remove \(|C|\) nodes in \(diam(T)\) cost. Refer Table 1, where \(D^{\prime}C(C^{*})\) is the cost per node for homing \(|C^{*}|\) nodes in Algorithm \(D^{\prime}\), \(D^{\prime}C(S-C^{*})\) is the cost per node for homing \(|S\setminus C^{*}|\) nodes in Algorithm \(D^{\prime}\), \(D^{*}C(C^{*})\) is the cost per node for homing \(|C^{*}|\) nodes in Algorithm \(D^{*}\) and \(D^{*}C(S-C^{*})\) is the cost per node for homing \(|S\setminus C^{*}|\) nodes in Algorithm \(D^{*}\). After \((k-1)\) iterations in \(M_{k}\), the tree becomes a star, which is the base case of both the algorithms. As mentioned above, \(D^{*}C_{o}=D^{\prime}C_{o}-1\) where \(D^{\prime}C_{o}\) is the cost computed in \(D^{\prime}\) and \(D^{*}C_{o}\) is the cost computed in \(D^{*}\), for every odd iteration. Therefore after the \(i\)th iteration, the total improvement is \(\lceil(i+1)/2\rceil\). The upper bound value for all millipede trees with diameters up to 16 was computed for both \(D^{\prime}\) and \(D^{*}\). The results (refer Table 2) show that, \(\delta^{*}\) is smaller than \(\delta^{\prime}\). \(\delta^{*}\) and \(\delta^{\prime}\) are deterministic for a millipede tree since the choice of vertices for deletion in each iteration does not alter the upper bound.