3
$\begingroup$

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

$\qquad \min(\#\text{leaves in } L(x), \#\text{leaves in } R(x))$

for $L(x), R(x)$ the left resp. right subtree of $x$, 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)$

I am actually looking for a subtle hint.

$\endgroup$
  • $\begingroup$ That's a basic question, if a nice one. What are your thoughts? Which kind of balance is referenced here? $\endgroup$ – Raphael Apr 12 '13 at 10:00
2
$\begingroup$

Traverse your graph in post order, create two auxiliary functions, $Cost$ and $Total$, first one demonstrates cost of your $g(x)$ at each vertex, second one calculates total number of leafs. set the cost function to zero: $Cost(leaf)=0$ for leaf, and $Total(leaf) = 1$ for leaf, then for parent node set this two functions as:

$$Cost(v) = min\{Total(child_l),Total(child_r)\}$$$$Total(v) = Total(child_l) + Total(child_r)$$

Because is post order, will be filled correctly and is $O(n)$ algorithm.

But actually worst case complexity in different algorithm may be differ, you can show that you cannot do this better than $\Omega(n)$, and above algorithm is $\Theta(n)$, which gives a tight bound, but, may be someone implement it in a bad way that causes to the $\Omega(n^9)$, or may be someone else provide an algorithm of $\Theta(n^3)$, At all, I mean your current question is not well defined, and if it was for real exam, it was wrong, and any answer which satisfies $\Omega(n)$ barrier, is correct.

$\endgroup$
2
$\begingroup$

Three questions that can lead you towards an answer:

  • In a binary search tree with $n$ nodes, how many leaves are there?
  • How often is each leaf "counted" by $g$?
  • How many predecessors does each leaf have?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.