# Lower bound for querying KD tree

In the book Computational Geometry, Algorithms and Applications there is an exercise asking:

In the proof of the query time of the kd-tree we found the following recurrence: $$Q(n)= \begin{cases}O(1), & \text { if } n=1, \\ 2+2 Q(n / 4), & \text { if } n>1 .\end{cases}$$ Prove that this recurrence solves to $$Q(n)=O(\sqrt{n})$$. Also show that $$\Omega(\sqrt{n})$$ is a lower bound for querying in a kd-tree by defining a set of $$n$$ points and a query rectangle appropriately.

The first part regarding the upper bound can be shown via the master method (the master method actually shows that this recurrence is $$\Theta(n)$$). However I am a bit uncertain about defining a set of points and a query rectangle that shows the lower bound.

Consider the example below where $$n=4$$. The points are the red dots, the median lines are the black lines, and the query rectangle is the blue rectangle. Does this show the lower bound, or do we need a more general construction since for $$n=4$$ we have $$\log_2(n) = \sqrt n$$?

No. To show a $$\Omega(\sqrt{n})$$ lower bound, it's not enough to show a lower bound for the single value $$n=4$$. I suggest you refer to the definition of big-Omega notation: https://en.wikipedia.org/wiki/Big_O_notation#The_Knuth_definition, https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition, How does one know which notation of time complexity analysis to use?.