@sanjaysharmarose **g(x) will take O(n) per level** ( __ not per node__ ) so T.C. will be (total no. of levels)*(T.C. per level) = O(log(n))*O(n) = O(n*log(n)).

Dark Mode

21,889 views

88 votes

A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is: $$\Large \min \left ( \substack{\text{number of leaf-nodes}\\\text{in left-subtree of $x$}}\;,\; \substack{\text{number of leaf-nodes}\\\text{in right-subtree of $x$}}\right )$$

Then the worst-case time complexity of the program is?

- $\Theta (n)$
- $\Theta (n \log n)$
- $\Theta(n^2)$
- $\Theta (n^2\log n)$

@sanjaysharmarose **g(x) will take O(n) per level** ( __ not per node__ ) so T.C. will be (total no. of levels)*(T.C. per level) = O(log(n))*O(n) = O(n*log(n)).

1

3

@ Bikram

“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”

Here when we see the recurrence relation that you proposed, how are we sure that there will be exactly n/2 leaf nodes in both left sub-tree and right sub-tree? like there can be n/3 leaf nodes in left sub-tree and 2n/3 leaf nodes in right sub-tree.

I hope you got my doubt!

0

102 votes

Best answer

B. At the root node (first level) the cost would be $\Theta\left(\frac{n}{2}\right)$ as the tree is **balanced**.

At next level, we have 2 nodes and for each of them cost of computing $g(x)$ will be $\Theta\left(\frac{n}{4}\right)$. So, total cost at second level $= \Theta\left(\frac{n}{2}\right).$ Similarly at **each level **(total cost per level and not the cost per node in a level) the cost would be $\Theta\left(\frac{n}{2}\right)$ and so for $\log n$ levels it would be $\Theta({n} \log n).$

PS: Even if we change $\min$ to $\max$ in the defintion of $g(x)$ we get the same answer.

@Pabitra

“min(number of leaf-nodes in left-subtree of x,number of leaf-nodes in right-subtree of x) “ is **COST** of computing g(x) not the g(x) itself. g(x) is itself not known.

Question is about finding time complexity of program which calculates g(x) for each node (we know the cost of calculating g(x) only).

n is no. of leafs.

By doing recursion we can find no. of leaf nodes at each subtree in O(n) and can be stored at each node.

Later calculate level wise total cost as explained above.

PS: Read answer below by Arjun Sir and all its comment for better understanding.

2

0

@hollow_mind Asymptotically ans should not change. As n is taken as total no. of nodes (tree being balanced BST)→

height of tree h = logn

max leaf = 2^h = Theta(n)

1

43 votes

Do a post order traversal and store and return $\min \left( \text{g}(x \rightarrow left), \text{g}(x \rightarrow right ) \right )$ for all non leaf nodes and store $0$ for all leaf nodes and return 1. BST being balanced, with n leaf nodes we can have total 2n nodes and complexity of tree traversal is linear in number of nodes- $\Theta(n)$.

But this is just computing the time complexity of $g(x)$ for each node- not exactly what is asked in question.

Actually the procedure I gave is computing the **COST of** computing the value of $g(x)$ which would have been correct had the question been defined as

$g(x) = \Large \min \left ( \substack{\text{number of leaf-nodes}\\ \text{in left-subtree of x}}\;,\; \substack{\text{number of leaf-nodes}\\\text{in right-subtree of x}}\right )$.

The correct answer for this would be $\Theta(n \log n)$ as at each level, the cost is $\Theta(n)$ and we have $\log n$ levels since the tree is balanced.

Correct Answer: $B$

0

20 votes

**1.if we use simple divide and conquer technique(without using extra space)**

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

**T(n)=2T(n/2)+1----->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=n*logn=O(nlogn)

**2.if we use extra memory to store no of leaf at left subtree and at right subtree for every node**

we don't need to go to last level for every node.

1.compute for every leaf node.

2.then use those values to compute at all nodes at (h-1) level till root.

so,** time complexity** of this method is equal to** O(n)**,since we are calculating value for each node and doing only one comparison.

**space complexity** is also** O(n)**,since we are using extra memory for every node.

since question is asking about** worst case time complexity**,so we have **O(nlogn)** .

16 votes

Let us assume a balanced binary tree containing n leaf nodes. We have to compute g(x) corresponding to every node x and the cost of computing g(x) is

min(number of leaf-nodes in left-subtree of x,number of leaf-nodes in right-subtree of x).

we start from root and compute g(x) corresponding to every node.g(root) = min(n/2 , n/2) = **Θ(n/2) =Θ(n).**

Cost at level 1 :**Θ(n).**

Cost corresponding to second level :

g(left_node)= min(n/4,n/4)=n/4

g(right_node)=min(n/4,n/4)=n/4

Total cost at level 2 :**Θ(n/4 + n/4) =Θ(n/2)=Θ(n)**

Similarly total cost at level 3 : **Θ(n/8 + n/8 +n/8 + n/8)=Θ(n/2)=Θ(n)**

...There are totally log n levels since it is a balanced binary search tree and cost at every level is **Θ(n).**

There fore time complexity of the program is **Θ(n) . log n =Θ(n logn).**

7