I’m trying to understand how the number of intersected areas by a vertical line in a KD-tree is equivalent to sqrt(n)
If you draw a balanced KD-tree with 7 nodes.
And then draw a vertical line l.
The number of areas this line intersects should be equivalent to sqrt(N) where N is amount of nodes. (7)
When I count the areas the vertical line L intersects I get 5. But sqrt(7) = 2,6 not even close.
Both sources get to the recurrence:
Which solves to O(sqrt(N)).
What am I doing wrong?