1
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jul 29 '13 at 8:16
4
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Feb 19 '14 at 18:16
  • $\begingroup$ Then can you tell me what is the average case time for that question? $\endgroup$ – loyola Feb 26 '14 at 10:21
  • $\begingroup$ 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. $\endgroup$ – David Richerby Feb 26 '14 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.