Quadtree performance

Question

Anyone knows where i can find some documentation on, or know how many operations insertion and queries takes in a quadtree?

wiki says O(logn) but i found another source saying O(nlogn) and i need to know which is true.

I'm working with a point quadtree

http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C http://en.wikipedia.org/wiki/Quadtree

Answer 1

Search: O(logn): it must traverse down the entire tree to find the element. To be specific the log in this case is log_4, as there are 4 children.

Insert(single point): O(logn): You must traverse the tree place to find the insertion location, then some small constant amount of work to split the points in that quadrant.

Insert(n points): O(nlogn), every point must inserted, leading to nlogn. I hope this is what the other site you read meant be nlogn, otherwise they would be very wrong.

The original paper is called "Quad trees a data structure for retrieval on composite keys" by Finkel and Bentley.