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

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

Why have they used $\Theta$ in the answer?
And why only $n$?

• You have posted a lot of questions recently that betray lack of fundamental skills. Please read the mathematical basics in CLRS again, and check out our related reference questions.
– Raphael
Jul 29 '13 at 8:16

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$.
• This doesn't really make sense. It's not because it's worst-case; rather, it's because (very informally), for large $n$, $n+\log n$ isn't a whole lot different from $n$. Given functions $f$ and $g$, whether $f\in \Theta(g)$ depends on how the functions grow, not on what they're being used to measure. Feb 19 '14 at 18:16
• It's not about best or worst or average or anything else. $O$, $\Theta$ and so on compare the growth rate of functions. It doesn't matter what those functions are used to measure: it could be running time or the number of apples in the store or anything else. Feb 26 '14 at 11:13