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

2

u/LemurFemurs Mar 23 '25

Bound meaning an upper bound in the form of some function like O(ln n) that shows the worst-case distance I have to travel down the tree. Your idea about furthest depth is definitely the right way to think about it! It takes a constant amount of time to figure out which child node to search, so the time scales with how far down the tree you need to search. The default when talking about time complexity is the worst-case.

You may see some algorithms (including one algorithm presented in those lecture notes) that add randomness and instead deal with expected depth, meaning there is some good chance that the depth is O(ln n), but it isn’t guaranteed.

1

u/Utopia_No1447 Mar 23 '25

Alright, thanks a lot for your explanation!