Gateforum Class Notes

Question

Suppose we have a balanced BST and we run a program on the BST with n leaf nodes and compute the value of a function $g(x)$ for each node in BST.

If the cost of computing $g(x)$ is minimum of number of leaf node in left subtree and number of leaf node in right subtree.

The worst case time complexity of the program is:

• A. $O(n)$
• B. $O(nlog_2n)$
• C. $O(n^2)$
• D. $O(n^2log_2n)$

Comments

What is the process for calculating

---

Please check the answer.

---

Duplicate of https://gateoverflow.in/1079/gate2004-85

Answer 1

It is balanced binary search tree .

We have total of logn levels (because tree is balanced) and cost at every level is O(n).

Hence total cost is= n*logn =O(n logn).

Alternatively:-

By using  Divide and conquer

we first need to count no. of leaf in left sub-tree, then no. of leaf in right sub-tree + compare them to find minimum.

T(n)=2T(n/2)+1   that gives complexity as O(n)

but we need to compute this for every node.

so, cost at 0 th level=O(n)

cost at 1st level=n/2+n/2=O(n)

cost at 2nd level=n/4+n/4+n/4+n/4=O(n)

we have total of logn levels (because tree is balanced) and cost at every level is O(n).

Hence total cost is  O( n log n)

Comments

Yeah got it