After a quadtree is fully created, why does comparison operation (for collision detection of n
objects) take linearithmic n log(n)
time? The nodes are recursively split by region/quadrant, and the search will scan down the tree, pruning off paths that aren't within the search coordinates, eventually finding or not finding target nodes within the bounds of the collided node. Each operation is comparing a divided partition n
, which seems like log(n)
time, not n log(n)
.
To find all collisions of n
objects (as well as to reveal any one collision in the worst case), one should perform about n
actions - check a vicinity of every object.
Every such checking, as you wrote, takes O(logn)
time, so overall time reaches O(nlogn)