-
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O (na logb n + mc logd n), the value of 10b + 100c + 1000d is _______.
-
- 110
- 21
- 11
- 111
Correct Option: A
It takes (log n) time to determine numbers n1 and n2 in balanced binary search tree T such that
1. n1 is the smallest number greater than or equal to L and there is no predecessor n¢ 1 of n1 such that n'1 is equal to n1.
2. n2 is the largest number less than or equal to H and there is no successor of n'2 of n2 such that is equal to n2.
Since there are m elements between n1 and n2, it takes ‘m’ time to add elements between n1 and n2.
So time complexity is O (log n + m)
So the given expression becomes O (n0 log' n + m' log0 n) And a + 10b + 100c + 1000d = 0 + 10 × 1 + 100 × 1 + 1000 × 1 = 10 + 100 = 110
Because a = 0, b = 1, c = 1 and d = 0
