The Complexity of the PLA Construction Algorithm (1/4)
Let n(X0, j) be the number of cells within a distance less or equal to j from X0, where n(X0, 0) = 1.
In the i-th iteration of the BFS algorithm, at most n(X0, i) vertices are considered.
An upper bound on the worst case complexity of the BFS algorithm is given by:
- S (X0, ƒä) = ƒÃƒäi=0 n(X0, i) .