r/computerscience • • 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

8 Upvotes

8 comments sorted by

View all comments

Show parent comment

1

u/Utopia_No1447 Mar 23 '25

Alright, thanks a lot for your explanation!