a) Create a recurrence relation T(n) describing the time taken by the countBST a

Question

a) Create a recurrence relation T(n) describing the time taken by the countBST algorithm called on a BST with n nodes. The structure of the BST is unknown. Assume for the recursive case that the left subtree has k nodes.

//A node has four fields: key, value, weight, and subtrees left and right.

//The only field of the special value EMPTY representing empty trees is //EMPTY.weight = 0.
function countBST(root)

if root != EMPTY
countBST(root.left)
countBST(root.right)

root.weight = root.left.weight + root.right.weight + 1

//A node has four fields: key, value, weight, and subtrees left and right.

//The only field of the special value EMPTY representing empty trees is //EMPTY.weight = 0.
function countBST(root)

if root != EMPTY
countBST(root.left)
countBST(root.right)

root.weight = root.left.weight + root.right.weight + 1

Explanation / Answer

Solution:

a)

Here are more than one cases,

The recurrence relaion for the given function is

Best case

T(n/2) + c

Worst case T(n) + c if the tree is skewed (if left skewed k= n and if right skewed k= 0)

b)

Base case:

If tree is empty weight is 0

which means if there are no nodes in the tree

T(0)= 0

Inductive step:

T(1)= 1

T(2)= 2

T(n)= T(n) + c, in worst case scenario

so we can

say that T(n)<= cn + d, where c and d are constants for values 1 and 1 respectively.

I hope this helps, please let me know in case of any doubt. Thumbs up if this helped.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.