Register

#Ace_Test_series.

• recategorized by
485 views
2 votes
2 votes

Consider the problem of construction of a minimum cost binary search tree for a given set of ‘$n$’ identifiers with their respective probabilities. The time complexity of the most efficient algorithm of the same is

  1. $O(n^2)$
  2. $O(n^3)$
  3. $O(n\log n)$
  4. $O(n^3\log n)$
• recategorized by
User Avatar

1 Answer

0 votes
0 votes

The identifiers and their probablities are assumed to be their weights. Thus forming new BST will take 

O(nlogn) time. Hence option C is correct

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
talha hashim asked Aug 17, 2018
501 views
ace test series
Consider the problem of construction of minimum cost binary search tree for a given set of 'n' identifiers with their respective probabilities.The time complexity of the most efficient algorithm of the same is___ A)0(n^2) B)0(n^3) C)0(nlogn) D)0((n^3)logn)
Consider the problem of construction of minimum cost binary search tree for a given set of 'n' identifiers with their respective probabilities.The time complexity of the ...
User Avatar
0 votes
0 votes
0 answers
2
`JEET asked Jan 19, 2019
1,049 views
#ACE_Test_Series
Consider the following instance of OBST (Optimal Binary search Tree) problem. N = 4; <$a_1$, $a_2$, $a_3$, $a_4$> = <do, if, int, while> P(1...4) = <3,3,1,1>; Q(0...4) = <2,3,1,1,1> The cost of OBST is________.
Consider the following instance of OBST (Optimal Binary search Tree) problem.N = 4; <$a_1$, $a_2$, $a_3$, $a_4$ = <do, if, int, while>P(1...4) = <3,3,1,1>; Q(0...4) = <2,...
User Avatar
1 votes
1 votes
1 answer
3
talha hashim asked Aug 17, 2018
621 views
ace test series
Consider the following instance of OBST (Optimal Binary Search Tree) Problem. n=4;<a1,a2,a3,a4>=<do,if,int,while> P(1....4)=<3,3,1,1>; Q(0....4)=<2,3,1,1,1> The Cost of OBST(optimal binary search tree) is________
Consider the following instance of OBST (Optimal Binary Search Tree) Problem.n=4;<a1,a2,a3,a4>=<do,if,int,while>P(1....4)=<3,3,1,1>; Q(0....4)=<2,3,1,1,1>The Cost of OBS...
User Avatar
1 votes
1 votes
1 answer
4
atul_21 asked Jan 2, 2018
1,219 views
Cost of Binary search tree
User Avatar
Link Copied!