recategorized by
31,149 views
118 votes
118 votes
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(n^a\log^bn+m^c\log^dn)$, the value of $a+10b+100c+1000d$ is ______.
recategorized by

8 Answers

3 votes
3 votes
within those m numbers, we have to search m times to see if the numbers are existing in the Balanced BST & add them.

so, m log n time.

c = 1, d = 1 => answer = 0 + 0 + 100 + 1000 = 1100
1 votes
1 votes

I have found an alternative solution, with ref to Coreman textbook exercise, Q.12.2-8. 

If you can prove this (solution: https://stackoverflow.com/questions/40561235/time-complexity-of-finding-k-successors-in-bst)
Then we know that since there are m nodes having value between L and H. We can also say that ‘m’ inorder successors of  node with value ‘L’.
So searching for L : O(log n)
‘m’ inorder successors : O(m+h) = O(m + log n) 
So overall time complexity : O(m + log n). a=1,b=1.c=1,d=0
Answer : 110.

0 votes
0 votes

We can firstly do inorder traversal of this Balanced BST which will result in sorted list of elements. It will take O(n).

No we can perform binary search on this sorted list to find L and H. It will take O(logn).

After finding L and H. We will run a loop to sum all elements between L and H. As there are m elements between L and H. So it will take O(m).

So total =O(n)+O(logn)+O(m) {As m<=n and O(n+logn)>=O(n)}

Hence we get O(n)

So a=1,b=0,c=0,d=0

So a+10b+100c+1000d =1+0+0+0=1

I am getting confuse whether I am thinking right or wrong So Please help...

edited by
0 votes
0 votes

I hope you understand it, Sorry for bad writing!

The reason that statement 3rd executing in O(m), since, we come across statement only when the if condition is true and it will only happen m times.

Answer:

Related questions

35 votes
35 votes
5 answers
4
go_editor asked Sep 28, 2014
8,745 views
Let $S$ be a sample space and two mutually exclusive events $A$ and $B$ be such that $A \cup B = S$. If $P(.)$ denotes the probability of the event, the maximum value of ...