edited by
544 views

3 Answers

0 votes
0 votes

i am not sure so, don't know about that balanced tree.

but ya 1 and 3 are correct.

0 votes
0 votes
I think that the answer 1 is correct.

1- heap sort complexity is nlogn which is polynomial bound.
2- I think we cannot make any unbalanced bst in logn rotations .

3- The time complexity of memorization and recursion or iterative method is same. No extra time will be needed.

SO according to me only first statement is true.
0 votes
0 votes
1) The time complexity is always O(n.logn) and hence, this statement is wrong.

2) COnsider a skewed tree. Now, if you want a complete balanced tree, the no of nodes in the bottommost level is approx  $\frac{n}{2}$

Each rotation will bring 1 node to the bottommost level . So, I think it will be O(n/2) = O(n)

3) Computing all the node values  results in extremely bad time complexity. DP and memoization(not memorization) results in O(no of nodes in the tree) time complexity.

Memoization is remembering previously computed values so that we dont do the same job again.

So, as per me, D is the right answer.

Related questions

1 votes
1 votes
2 answers
1
akankshadewangan24 asked Sep 20, 2018
841 views
If t(n) and s(n) denotes the time and space complexity of an algorithm with input size n element then which one of the following is always true?S(n)=O(t(n)) correct H...
0 votes
0 votes
3 answers
2
Subham Nagar asked Mar 20, 2018
1,179 views
An array $'A'$ has $n$ distinct integers. What is the tightest time complexity to check $A[i]=i$ for some $i$. Consider all elements of array within range from $1$ to $n$...
0 votes
0 votes
0 answers
3
Kai asked Jan 29, 2017
422 views
Time complexity of the given program is?
1 votes
1 votes
1 answer
4