## 4 Algorithm Analysis
### Complexity Analysis
#### 4.2.2 Time Complexity  
At the beginning of the uneven clustering, each node synchronously produces a random number from zero to one and estimates itself to be a provisional cluster head node or not, and then, each of the provisional cluster head nodes synchronously broadcasts its status message. The time complexity of these operations is constant. In the cluster head competition phrase, a provisional cluster head node may become a final cluster head node, which needs to compare the distance to the sink node with all of its competition neighbor nodes or exit the competition. For the convenience of expression on time complexity, the number of competition neighbor nodes of a provisional cluster head node is expressed by the average number of competition neighbor nodes in the network, signed as \(N_{a}\). Consequently, the time complexity of the operation that a provisional cluster head node becomes a final cluster head node is \(N_{a}\), and the time complexity of the operation that it exits competition is constant. However, the worst situation in the phrase is that each of them judges itself to be a final cluster head node or not in the one-by-one way, and the time complexity of the situation is \(N_{a}\times K_{c}+N_{p}-K_{c}+2\). At the end of the uneven clustering, each non-cluster head node joins a final cluster head node that is the nearest to it. The worst situation is that an ordinary node receives \(K_{c}\) messages from all final cluster head nodes, so that it will compare the distance \(K_{c}\) times; consequently, the time complexity is \((N-K_{c})\times K_{c}\). Thus, the time complexity of the uneven clustering is formulated as Expression (21), _i.e._, \(O(N^{2})\).  
\[N_{a}\times K_{c}+N_{p}-K_{c}+(N-K_{c})\,K_{c}+2<N^{2}+N_{p}-K_{c}+N^{2}+2 \tag{21}\]  
During the process of the path selection, the worst situation is that each cluster head node selects ordinary nodes within \(R_{c}\_Max\) as its next-hop node. In this situation, the time complexity of the \(i\)-th cluster head node is \(N_{i}\). Thus, the time complexity of the total process is \(\max(N_{i})\), _i.e._, \(O(N)\), because each cluster head node finds its next-hop node synchronously.  
In the phrase of in-cluster nodes' position adjustment, the cluster head node calculates the depth of every in-cluster node. Assuming that the \(i\)-th cluster has \(N_{i}\) in-cluster nodes, the worst situation is that an in-cluster node has \(N_{i}\) basic nodes, and for every basic node, the cluster head node should calculate the \(CRR\) of \(2R_{c}\_Max\) positions. Then, it may select the minimum \(CRR\) from the \(CRR\) of \(N_{i}\) basic nodes. What is worse, there are \(N_{i}\) basic nodes whose \(CRR\) is within _rang_ range of the minimum \(CRR\); in other words, the cluster head node should select the basic node with minimum hops from \(N_{i}\) basic nodes. Thus, the time complexity of the whole process is formulated as:  
\[\begin{split}\sum\limits_{i=1}^{K_{c}}N_{i}\left(2R_{c}\_Max \times N_{i}+N_{i}+N_{i}\right)&=(2R_{c}\_Max+2)\sum\limits_{i=1 }^{K_{c}}N_{i}^{2}\\ &<(2R_{c}\_Max+2)\left(\sum\limits_{i=1}^{K_{c}}N_{i}\right)^{2} \\ &=(2R_{c}\_Max+2)\,N^{2}\end{split} \tag{22}\]  
That is, the result is \(O(N^{2})\).  
Finally, the time complexity of URSA is \(O(N^{2}+N+N^{2})\), _i.e._, \(O(N^{2})\).