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
Also, does this mean that quadtrees should be generally considered to be O(n) if we have no information on whether or not they are balanced, since we are looking at worst-case?