edited by
31,453 views
103 votes
103 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?

  1. $\Theta (n)$
  2. $\Theta (n \log n)$
  3. $\Theta(n^2)$
  4. $\Theta (n^2\log n)$
edited by

11 Answers

0 votes
0 votes
n = Number Of Leaves in the tree

Height of Tree = log(No of Leaves) for a Balanced Tree = logn

=> Any node in second last lvl will have 1 leaf in left subtree , and there are (n/2) such nodes.
=>Any node in third last lvl will have 2 leaves in left subtree , and there are (n/4) such nodes.
=>Any node in fourth last lvl will have 4 leaves in left subtree , and there are (n/8) such nodes.
And so on.............. Again remember 'n' is the no of leaves.

So total time = 1*(n/2) + 2(n/4) + 4(n/8) + 8(n/16) +.......
                        =(n/2) + (n/2) + (n/2) + (n/2) + ........logn times. , bcoz no of lvls = log n
                        = (n/2) logn
                        
                        =O(nlogn)
0 votes
0 votes

It is BBST so the height of the tree is logn.

  • starting from the root it have n/2 and n/2 leaves.min of this is n/2.
  • from the next level, it has n/4 from the left side and n/4 from the right side so n/4 + n/4 = n/2 and so on till last level.
  • therefore n/2*Θ(long)=Θ(nlogn)
edited by
0 votes
0 votes

A proper approach to a question is obtained by first analyzing the question properly. Let us do it first.

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:
$$\text{min(number of leaf-nodes in left-subtree of x,number of leaf-nodes in right-subtree of x)}$$

Then the worst case time complexity of the program is?

Here it is already given that the function $g(x)$ has cost which is equal to the minimum of the no. of leaves in its left subtree or right subtree. So there is no question of finding the no. of leaves in the left and right subtree of the nodes $x$ given as input to function $g$.

Possibly $g$ is a helper function in a program and as per implementation, the nodes in the balanced binary search tree are already pre-processed (probably) and $g$ probably uses that information and does what it has do to.

Now in the question it is asked to find the worst-case time complexity of the program. Now the program accepts balanced binary search trees. But the worst case behavior is exhibited when the input given to the program is a complete binary tree with $n$ leaf nodes as shown in the picture below:


 

In the picture above the last level has $n$ leaves.

In level $0$ we have $1$ nodes.

In level $1$ we have $2^1$ node.

In level $h$ we have $2^h$ nodes.

So $2^h=n \implies h=\lg n$

Each of the nodes at level $h-1$ has $1$ leaf node in the left as well as right subtree. So for each node cost is hence $1$.

Each of the nodes at level $h-2$ has $2$ leaf node in the left as well as right subtree. So for each node cost is hence $2$.

Generalizing, Each of the nodes at level $h-i$ has $2^{i-1}$ leaf node in the left as well as right subtree. So for each node cost is hence $2^{i-1}$.

Now each level $l$ has $2^l$ nodes. Also $l=h-(h-l)$ so cost for each node at level $l$ is $2^{h-l-1}$ from the previous generalization. Hence we have total cost:

$$\text{Cost =} \sum_{l=0}^{h-1} 2^l \times 2^{h-l-1}=\sum_{l=0}^{h-1} 2^{h-1}=(h)(2^{h-1})=(\lg n )\frac{n}{2}=\Theta(n \lg n)$$

Answer : (B)

Answer:

Related questions

27 votes
27 votes
6 answers
9
Kathleen asked Sep 18, 2014
22,413 views
The following numbers are inserted into an empty binary search tree in the given order: $10, 1, 3, 5, 15, 12, 16$. What is the height of the binary search tree (the heigh...
62 votes
62 votes
4 answers
11
55 votes
55 votes
8 answers
12