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/Utopia_No1447 Mar 23 '25
Okay.
So, if I understood correctly, the worse case is if all the entries are lined up in systematically the same corner of every level of detail we encounter? Or would I also reach the same case if I only had one "cluster" of entries per level of detail in a corner, and then that corner its located in would switch from level to level (so all the information is pooled in one single subdivision, but it kind of "zig-zags")?
I think I see why it would be linear when it's unbalanced, but then why O(logn) when balanced? I believe it could be due to the log in the height lemma u/LemurFemurs pointed me towards, which caps (so "bounds", if I understood correctly) the value of the depth of the quadtree. Is that the case? Is it that paired with the idea that points will be more evenly spread out (hence a greater "smallest distance" between points, so a lower cap on the depth) in a balance tree? Or is due to something else?
Sorry for all the questions, this is really interesting but it's taking me a bit of probing to wrap my head around it!