The analysis of the neighbor finding routines in the `Resize`
function is performed by calculating the number of nodes that are
visited in the process. For the purpose of the `Resize` function
only the nearest common ancestor is needed. The algorithm climbs up
the tree until the lowest G-Node in the direction of the resize that
is not the first or last child is returned, depending on the
direction. Thus, the nodes at every other level are examined. In the
worst-case, half of the nodes up the root need to be traversed, which
costs *O*(*d*/2), d is the depth of the tree.

For an average case analysis, let's assume that the tree has *w*
children at each node, and thus the depth of the tree is
. Assume that the node is at index *i* and at level
*j*. With probability , it is the first or last child,
with probability it is in between. Thus, the number of
nodes to be examined is as below:

This can be simplified to yield , which is as j goes to infinity.

The `FindWindow` function makes a point query, i.e. given the
coordinates of a point finds the lowest-level rectangle it
encapsulates. The algorithm, starting form the root node, traverses
the tree down in the hierarchy on encapsulating nodes. Assuming, that
each node has *w* children, in the worst case it costs
if a linear search is made when determining the
overlapping window over each children nodes. Performing a binary
search will be much faster especially when *w* is large, in which case
the algorithm performs in ,
i.e. , actually independent on the number children on
the average.

Sun Sep 13 18:34:46 EDT 1998