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.