The Complexity of the PLA Construction Algorithm (2/4)
In reality, the number of nearest neighbor of a cell is bounded by some constant, and so is the density of cells per area unit.
Thus, the maximal number of cell reachable within t time-slots is O(t2), and the worst case complexity of the BFS is therefore:
- S (X0, ƒä) = ƒÃƒäi=0 O(i2) = O(ƒä3) .