## 7 Complexity
### Theoretical Analysis  
In the following, we assume the worst configuration from which our algorithm can start. Then we study the complexity of DC2 HC. There is a known configuration from which DC2 HC fails to provide good results (the worst-case scenario). This scenario is when nodes are related and organized in a straight line and their \(IDs\) are monotonically increasing or decreasing as illustrated in Figure 11. In this configuration (network with low density), the maximum degree of each node \(i\in G\) is: \(0<Deg(i)\leq 2\). In this case, network nodes will have the same weight and the election of cluster head depends on nodes \(IDs\). Although, this configuration is unlikely to occur in a real-world network. It will allow the computation of the complexity in the worst case. In the following, we prove that the time complexity of DC2 HC is at most \(O(|V|+k)\) rounds, where \(|V|\) is the number of nodes on the network. Figure 11: Worst-case scenario (\(k=2\)). **Lemma 4**. : _Let \(i\) be the node with highest weight in \(G\) then:_  
1. _After 2 rounds and in all following rounds,_ \(i\) _is a cluster head (_\(Mych_{i}=ID_{i}\)_and_ \(Dist(i,\,Mych_{i})=0\)_)._
2. _After_ \(2\times k+2\) _rounds and in all following rounds, the neighbors of node_ \(i\) _at distance_ \(\leq k\) _form a cluster, where_ \(\forall j\in N_{\leq k}(i):(Mych_{j}=i)\wedge(Dist(i,j)\leq k)\)_._  
Proof. : First, we demonstrate that (a) is true. In the first round, as \(i\) is the node with the highest weight in \(G\), it has the high weight value among all its neighbors. \[\forall j\in V-\{i\},\,z\in N(i):(W_{i}>W_{j})\Rightarrow(W_{i}>W_{z})\]  
This node executes rule R1 to become a CH. In the second round, \(i\) executes rule R2 to update the distance value \(Dist(i,Mych_{i})=0\). After that, no more rules are activated at node \(i\), so it will not execute another move in the following rounds. Property (b) means that the sub-graph \(G^{{}^{\prime}}=\{i\bigcup N_{\leq k}(i)\}\) that contains node \(i\) and its neighbors at distance \(\leq k\) reaches a stable state after at most \(2+2\times k\) rounds. In the 3 rd round, when node \(i\) finishes its execution, rule R1 will be enabled for its neighborhood. These neighbors join the cluster of node \(i\). Next, they execute R3 to update their distance \(Dist(i,Mych_{i})=1\) (round 4). After round 4, no more rules can be activated in the neighborhood of \(i\), so they will not execute other movements in the following rounds. The argument given above is repeated for the neighbors at distance \(\leq k\) from \(i\) (i.e., neighbors of \(i\) will reach a stable state after \(2\times k\) rounds). Therefore, to form a cluster, two rounds are required to elect the CH and \(2\times k\) rounds to form the cluster. By induction, each node with the highest weight and its neighbors finish their execution after at most \(2+2\times k\) rounds. **Lemma 5**. : _The maximum number of clusters that can be generated with DC2 HC in the worst case configuration is \(1+n/(k+1)\) where \(n=|V|\)._  
Proof. : DC2 HC divides the graph \(G\) into several spanning trees where each tree has the node with the highest weight as its root (the cluster head) and its neighbors at a distance \(\leq k\) represent the rest of this tree (cluster). Therefore, the minimum number of nodes that can be in a cluster is \(k+1\). In the worst-case scenario (the graph shown in Figure 11), a related graph can contain \(n/(k+1)\) clusters. As each cluster is represented by only one CH, the graph can contain at most \(n/(k+1)\) cluster heads. One is added to the previous threshold to cover the case where \(n\ mod(k+1)>0\). Thus, we obtain \(\big{[}\frac{n}{k+1}\big{]}+1\), which represents the maximum number of CHs formed by DC2 HC in the worst-case configuration. **Lemma 6**. : _DC2 HC algorithm converges after at most \(2\times(n+k+1)\) rounds._  
Proof.