1.2k views

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 | 1.2k views

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)$
edited by
sir ,but in case of skewed bst height will be n.2^n then the tn=n.2^n
Yes. That's true. But here question specifies "balanced".
yeah sir i got it..
How binary search takes 0(logn) time in worst case?? it is 0(n). Someone please explain
It is not simple binary search tree ,it is Balanced binary search tree for ex AVL tree which takes O(logn) in worst case.