Worst case running time to search for an element in a balanced BST with $n2^n$ elements What is the worst case running time to search for an element in a balanced binary search tree with $n 2^n$ elements?

The answer is $\Theta(n)$.

My answer:

To search an element in BST is $\log (n)$ so
$$
\begin{align*}
\log(n 2^n ) &amp;=  \log(n) + \log(2^n) \\
            &amp;=  \log(n) + n\log 2 &amp; \text{(base is 2)} \\  
            &amp;=  \log(n) + n  
\end{align*}
$$


  Why have they used $\Theta$ in the answer?
  And why only $n$?
You state that searching an element in a BST takes time $\log n$, but this is wrong on two counts. First, this is (roughly) the worst-case number of comparisons. Second, the running time itself isn't exactly $n$ but is roughly $C\log n$ for some constant $C$ that depends on the exact machine model (assuming that comparisons take constant time). For this reason, it is better to use $\Theta$ notation (look it up!) and state that the worst-case running time of element lookup in a BST is $\Theta(\log n)$, where $n$ is the number of elements in the BST.

In our case, the number of elements is $n2^n$, and so the running time is $\Theta(\log(n2^n)) = \Theta(\log n + n) = \Theta(n)$. Asymptotically, $n + \log n = \Theta(n)$, and so there is no need to explicitly mention $\log n$.