## 3 Algorithmic Mathematical Analysis
### Algorithm Complexity Analysis  
**Greedy algorithm:** For the source node, it only needs to find the next jump node with the shortest path in each step until it reaches the target node. At most, \(\mathrm{N}-2\) nodes are passed through from the source node to the target node, and the average expectations are \(\frac{N-2}{2}\) nodes. Every time the information arrives at one node to find the next node, N nodes need to be traversed to calculate the locally optimal path [17]. Its computational complexity is:  
\[\mathrm{G(N)}=\frac{(\mathrm{N}-2)\cdot\mathrm{N}^{3}}{2} \tag{1}\]  
**Flooding and backtracking algorithm:** Its computational complexity is:  
\[\mathrm{F(N)}=\sum_{\mathrm{m}=0}^{\mathrm{N}-2}\frac{(\mathrm{N}-2)!}{( \mathrm{N}-2-\mathrm{m})!}\cdot\mathrm{N}^{2}+\delta_{1} \tag{2}\]  
In this formula, \(\frac{(\mathrm{N}-2)!}{(\mathrm{N}-2-\mathrm{m})! }\) is the number of satellite nodes to be traversed when the source node passes m forwarding satellites. It can be deduced that finding the routing path from the source node to the destination node takes \(\sum\limits_{\mathrm{m}=0}^{\mathrm{N}-2}\frac{(\mathrm{N}-2)! }{(\mathrm{N}- 2-\mathrm{m})! }\) calculations. There are \(\mathrm{N}^{2}\) paths to calculate here. \(\delta_{1}\) is a positive number tending to be infinitesimally small, which represents the backtracking part of the flooding algorithm. Only when more than one path with the same distance is founded during traversal, backtracking is performed to compare the number of nodes that pass through and select the path with fewer nodes. However, this situation is very rare and can almost be ignored [18; 19]. **Partition routing algorithm:** For the source node, the destination node has a chance of \(\frac{\mathrm{N}-1}{N-1}\) being in the same group and a chance of \(\frac{\mathrm{2N}}{N-1}\) being outside the group [20]. For stars nodes within the same group, its computational complexity is:  
\[\sum_{\mathrm{m}=0}^{\frac{\mathrm{N}-2}{\mathrm{e}}-2}\frac{\left(\frac{ \mathrm{N}}{3}-2\right)!}{\left(\frac{\mathrm{N}}{3}-2-\mathrm{m}\right)!}+ \delta_{2} \tag{3}\]  
For stars nodes outside the group, its computational complexity is:  
\[2\cdot(\sum_{\mathrm{m}=0}^{\mathrm{N}-1}\frac{(\frac{\mathrm{N}}{3}-2)!}{( \frac{\mathrm{N}}{3}-2-\mathrm{m})!}+\delta_{2})\]  
\[\delta_{2}=\delta_{\mathrm{recall}}+\delta_{\mathrm{greed}}\]  
\[\delta_{\mathrm{greed}}=\frac{\left(\frac{\mathrm{N}}{3}-2\right)\cdot\frac{ \mathrm{N}}{3}}{2} \tag{4}\]  
Both partial flooding algorithms and greedy algorithms are used to calculate the path within the group. \(\delta_{\mathrm{recall}}\) refers to the overhead of the backtracking part of the flooding algorithm. \(\delta_{\mathrm{greed}}\) represents the overhead of the greedy algorithm. Compared with the huge calculation time cost of the flooding algorithm, the time cost of the greedy algorithm and backtracking can almost be ignored [21]. Hence, the average computational complexity of the total algorithm is:  
\[\text{P(N)}=(\frac{\frac{N}{3}-1}{N-1}\cdot\sum_{m=0}^{\frac{N}{N}-1}\frac{ \left(\frac{N}{3}-2\right)!}{\left(\frac{N}{3}-2-m\right)!}+\delta_{2}+\frac{ \frac{2N}{3}}{N-1}\cdot(\sum_{m=0}^{\frac{N}{N}-1}\frac{\left(\frac{N}{3}-2 \right)!}{\left(\frac{N}{3}-2-m\right)!}+\delta_{2})\cdot\!2)\cdot\!\text{N}^{2} \tag{5}\]  
**Balanced partition routing algorithm**: In contrast to the partition routing algorithm, a balanced partition routing algorithm adds the process of dynamically calculating communication nodes between the groups.