GATE CS 2012 Q5 — Binary Search Trees

The worst-case running time to search for an element in a balanced binary search tree (BST) with $N$ elements is proportional to its height, which is $\Theta(\log N)$.

Given that the number of elements is $N = n 2^n$, we can substitute this into the time complexity expression:

Using the properties of logarithms:

Assuming the base of the logarithm is $2$:

As $n \to \infty$, the term $n$ dominates $\log_2 n$. Therefore:

Thus, the worst-case running time is $\Theta(n)$, which corresponds to option C.