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)

Category: QuestionsWhat 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)
Editor">Editor Staff asked 1 month ago

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.

1 Answers
Editor">Editor Staff answered 1 month ago

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