I’m currently reading up on the time complexity of the range search/query for an unbalanced KD-tree.
I see all these different articles where the same the complexity is O(sqrt(N)) where N is the number of points. And this order of growth is proportional to the number of points a vertical line can intersect with in a KD-tree. But if we create a KD-tree with 7 points, the MAX intersects points from a vertical line should be sqrt(7) = 2,64. Let’s assume that it’s rounded up to 3. While drawing the some “test” kd-tree’s you see this relation is true. But when you draw unbalanced kd-trees, this is not true.
How would you go about analyzing the range search complexity of an unbalanced KD-tree?
My thoughts: An unbalanced KD-tree would be O(N) since the points/nodes are aligned to one side(Like a linked-list)