recategorized by
456 views
0 votes
0 votes
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)
recategorized by

1 Answer

1 votes
1 votes

From the recurrence,

we have the following memoized algorithm.
 

In order to compute the actual BST, for each subproblem we can also store the root of the corresponding subtree.

There are a total of n2 subproblems, and each subproblem takes O(n) time to compute, assuming all its subproblems are already solved. Thus, the total running time is O(n3 ).

Reference: http://www.cs.cmu.edu/afs/cs/academic/class/15750-s17/ScribeNotes/lecture7.pdf

Related questions

2 votes
2 votes
1 answer
1
`JEET asked Jan 19, 2019
477 views
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 complexit...
1 votes
1 votes
1 answer
2
talha hashim asked Aug 17, 2018
606 views
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...
0 votes
0 votes
1 answer
3