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$?

enter image description here


1 Answer 1


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?.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.