GATE CS 2004 Q85 — Binary Search Trees

To find the worst-case time complexity of computing $g(x)$ for all nodes in a balanced binary search tree with $n$ leaf nodes, we can set up a recurrence relation.

Let $T(n)$ be the total cost of computing $g(x)$ for all nodes in a balanced BST with $n$ leaf nodes.

1. Cost at the root node: Since the binary search tree is balanced, the $n$ leaf nodes are distributed almost equally between the left and right subtrees. Thus, the left subtree has approximately $\frac{n}{2}$ leaf nodes, and the right subtree has approximately $\frac{n}{2}$ leaf nodes.
   The cost of computing $g(\text{root})$ is: $$\text{Cost}(\text{root}) = \min\left(\frac{n}{2}, \frac{n}{2}\right) = \Theta(n)$$
2. Recursive step: The total cost $T(n)$ is the sum of the cost at the root and the costs of computing the function recursively for the left and right subtrees: $$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$$

Using Master's Theorem for the recurrence $T(n) = aT(n/b) + f(n)$ where $a = 2$, $b = 2$, and $f(n) = \Theta(n)$:

Since $\log_b a = \log_2 2 = 1$, and $f(n) = \Theta(n^1)$, we fall into Case 2 of Master's Theorem. Therefore:

Thus, the worst-case time complexity of the program is $\Theta(n \log n)$.