For a balanced Kd-tree, the average complexity of a K-nearest neighbor (KNN) search is $𝑂(log⁡𝑁+𝐾)$

where:

1. $N$ is the number of points in the dataset.
2. $K$ is the number of nearest neighbors to find.

In the worst case, where the dataset has a high dimensionality or is highly skewed, the search can degrade to $𝑂(𝑁)$

Effect of Dimensionality

1. For low-dimensional spaces (e.g., 2D or 3D), Kd-trees are efficient.
2. As the number of dimensions $d$ increases, the efficiency drops.
3. In very high dimensions $(𝑑≫10)$, the Kd-tree may perform almost as poorly as a brute-force search.