Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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 ) &= \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 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$.
In question, they are asking only the worst case time,so, they comparing log n(log base 2) time with n time. So, the worst case time is n becasue n is larger than the log n time..
