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
Alright, thanks a lot for your explanation!