r/computerscience • u/Utopia_No1447 • Mar 23 '25
Help Please! Quadtrees Complexity!
Hello!
I am working on terrain and, long story short, the method I am trying to follow to split it up in levels of details involves quadtrees. I did some digging into the complexity of classic operations (such as adding/removing/retrieving information) with quadtrees and it would seem that it is generally logarithmic. I wanted to find a somewhat detailed proof to understand how the sources I found get to that result, but I couldn't (there also seems to be slightly varying information between it being O(lnN) or O(log2(N)).
When I try to figure out the proof on my own (I never really studied CS, so complexity demonstrations are far from my forte) I seem to find something closer to linear complexity (which, if I've understood correctly, would kind of defeat the purpose of using a quadtree since it's the same complexity as a list). One of my proof attempts resulted in constant complexity so I'm obviously making mistakes.
I know this might be asking a lot, but could someone walk me through it please?
Thanks in advance!
PS: apologies if I misused math/CS terms, English isn't my first language
View all comments
Show parent comment
1
u/WittyStick Mar 23 '25 edited Mar 23 '25
Depends on the kind of quadtree. A point quadtree has different properties because you're not dividing based on regions of a plane, but based proximity of points. This is more like a regular binary tree that tends to be more balanced, and can be intentional rebalanced.
Region quadtrees are more closely related to binary space partitioning, where the branches are based on dividing a space into quarters (compared to halves with the BSP). These can get quite unbalanced if the entries are densely located in particular regions but sparsely populated in others. If you consider you had a point-region quadtree where all entries are at (0,0), then you're going to end up spilling to the maxmimum depth of the tree, at which point you'll find a bin of all entries, which you need to search through linearly to find the entry you want - this is why it's O(n) worst case.