The first loop in find-poly() reduces to
while O(n)
O(1)
foreach O(n)
O(log n)
which reduces completely to O(n2 log n).
O(n2) edges can be turned into a graph in O(n2) time. A depth-first
search of a graph with v vertices and e edges takes O(v +
e) time; chains() then takes O(n2) time.
The second find-polys() loop
polys = { }
foreach e in edges
polys += chains(e->second)
runs in O(n4) time, which is a drag, because that's little better than the polygon-generating solution. But, let's take a closer look.
The worst-case size of edges is n2 when each edge has a different
length from all other edges. However, in that case, each bucket contains one
edge, and chains() runs in constant time. In the other direction, the worst
case for chains() occurs when all n2 edges are in the same bucket
(that is, they all have the same length). In that case edges contains one
element.
In either case, the second loop can be argued to have O(n2) behavior, and
find-polys() itself has O(n2 log n) behavior.
This page last modified on 28 April 2004.