# Efficient Wireless Charger Deployment for Wireless Reshapeable Sensor Networks
## 5 Analysis  
### Algorithm Time Complexity Analysis  
In this subsection, we analyze the time complexity of the two proposed algorithms. In the GCC algorithm, for every grid point \(g\), a half sphere \(HS\) centered at \(g\) of radius \(D\) is formed (Lines 3-4). If \(S\) covers \(k\) sensor nodes, then candidate cones are generated on a node-pair-by-node-pair basis (Lines 9-17). There are up to \(4C_{2}^{k}\) candidate cones that can be generated, where \(k\leq n\). Since there are \(m\) grid points, the number of candidate cones generated is then \(4 mC_{2}^{k}\leq mn^{2}=O(mn^{2})\) and the time complexity to generate the candidate cones is also \(O(mn^{2})\). On each iteration in the repeat-until loop (Lines 18-24), the GCC algorithm first selects the cone \(c\) from \(CS\) that covers most unmarked nodes in \(NS\) (Line 19). Since there are at most \(mn^{2}\) cones in \(CS\), and the algorithm should check if a cone can cover all nodes, the selection can be done in \(O(mn^{3})\) time complexity. The GCC algorithm then checks if every unmarked node covered by cone \(c\) can be marked after updating its energy requirement (Lines 21-23). The checking takes \(O(n)\) time complexity. A cone can be selected only once in the repeat-until loop, so there are at most \(O(mn^{2})\) iterations in the loop. In summary, there are \(O(mn^{2})\) iterations in the repeat-until loop, and each iteration's time complexity is \(O(mn^{3})\) (Line 19). Thus, the time complexity of the loop is \(O(m^{2}n^{5})\). Since the repeat-until loop has the highest time complexity in the algorithm, we thus have that the time complexity of the GCC algorithm is \(O\) (\(m^{2}n^{5}\)).  
The ACC algorithm forms a half sphere \(HS\) centered at \(g\) of radius \(D\) for every grid point \(g\) (Lines 3-4). If \(HS\) covers \(k\) sensor nodes, then \(k\) candidate cones will be generated, \(k\leq n\) (Line 8). Every candidate cone is tested for possible direction adjustment for \(k\) times (Lines 9-15), so there are \(k^{2}=O(n^{2})\) adjustment tests. Since there are \(m\) grid points, the ACC algorithm forms \(m\) half spheres. Let the half spheres cover \(k_{1},\ k_{2},\ldots,\ k_{m}\) sensor nodes, respectively. Thus, the total number of candidate cones is \(\sum_{i=1}^{m}k_{i}\leq mn=O(mn)\) and the total number of adjustment tests is of the time complexity \(O(mn^{3})\). On each iteration in the repeat-until loop (Lines 16-22), the ACC algorithm first selects the cone \(c\) from \(CS\) that covers the most unmarked nodes in \(NS\) (Line 17). Since there are at most \(mn\) cones  
Figure 9: Illustration of candidate cone direction adjustment by composing two vectors.  
in \(CS\), and the algorithm should check if a cone can cover all nodes, the selection (Line 17) can be done in O(\(mn^{2}\)) time complexity. The ACC algorithm then checks if every unmarked node covered by cone \(c\) can be marked after updating its energy requirement (Lines 19-21). The checking takes O(\(n\)) time complexity. A cone can be selected only once in the repeat-until loop, so there are at most O(\(mn\)) iterations in the loop. Thus, the time complexity of the repeat-until loop is O(\(m^{2}n^{3}\)). Since the repeat-until loop has the highest time complexity in the ACC algorithm, the time complexity of the ACC algorithm is O(\(m^{2}n^{3}\)).