2
$\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 min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then what is the worst case time complexity?

Since $g(x)$ is applied on the 2 halves of the binary tree, I guess the recurrence relation must look something like :
$$T(n) = 2T\Big(\frac{n}{2}\Big)+k$$
What I could understand from the question is that $g(x)$ is applied on all the $n$ nodes and instead of $k$ it must be something of the order $O(n)$ but I'm not sure what it is. Am I heading in the right direction?

$\endgroup$
  • 1
    $\begingroup$ Why would that be the worst case? Trie to express the true cost as recurrence and estimate that then. Note that "halves" is not right here; most notions of balancedness to not assert that exactly half the number of nodes are in each subtree. In fact, height-balanced trees are per se not even weight-balanced, so the ratio can be arbitrarily bad (AVL, Red-Black). $\endgroup$ – Raphael May 7 '15 at 9:26
1
$\begingroup$

Hints:

Can you make a guess? If you can make a guess, can you prove it?

What do you know about the height of a balanced search tree?

If the entire tree has $n$ nodes, what can you say about the number of nodes in the left subtree? What is the smallest it could be? The largest it could be? What about the right subtree?

Can you derive a recurrence relation?

Imagine you treat the cost of computing $g(x)$ to be measured in dollars, and you charge \$1 to each node in the right/left subtree (whichever is smaller) to account for the cost of computing $g(x)$. For any given node, what can you say about how many dollars it is charged?

If you know about amortized analysis, you might review that material.

It's not clear to me what $k$ represents in your proposed approach or where you got that recurrence relation. Why don't you try harder to work out what recurrence relation might be suitable and what its solution is?

$\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.