The Complexity of the PLA Construction Algorithm (4/4)
The number of iterations required can be reduced to x = [Ċ / k] + 1, where in each iteration the BFS is extended by a distance k.
The worst case complexity, under this assumption is O(k2x3) „f ƒä 3 / k.
This is still O(Ċ 3), but the computational task is reduced by a factor k.