Question

What will be the time complexity of query operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (k = number of bins query rectangle intersects)

(a) O(1)

(b) O(k)

(c) O(k^2)

(d) O(log k)

Query is from Trees topic in section Trees of Data Structures & Algorithms I

This question was posed to me in examination.

Answer 1

Right answer is (b) O(k)

The best I can explain: The process of query becomes faster in a case when the number of candidates are equally distributed among the bins. In such a case the query operation becomes O(k).