recategorized by
13,303 views
50 votes
50 votes

The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is

  1. $\Theta(n\log n)$
  2. $\Theta(n2^n)$
  3. $\Theta(n)$
  4. $\Theta(\log n)$
recategorized by

2 Answers

Best answer
92 votes
92 votes
Balanced binary search takes $\Theta(\log n)$ for $n$ elements in the worst case. So, with $(n2^n)$ elements, the worst case time will be

$\Theta(\log (n2^n)) $

   $= \Theta(\log n + \log 2^n) $

   $= \Theta(\log n + n) $

   $=\Theta(n)$

Correct Answer: $C$
edited by
6 votes
6 votes

The worst case running time to search for an element in a balanced binary search tree with n elements is  log(n) because Balanced search tree have height logn

for n2 elements replace  n2n in place of n     

Θ(log(n2n))

   =Θ(log⁡n+log⁡2n)

   =Θ(log⁡n+nlog2)

   =Θ(log⁡n+n)

   =Θ(n)

Answer:

Related questions

48 votes
48 votes
7 answers
3