7,892 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)$

ALWAYS REMEMBER:  BALANCED BINARY SEARCH TREE = AVL TREE

Note:
Binary Search Tree and Balanced Binary Search Tree is 2 different things.
All Binary Search Tree need not be Balanced however the vice versa is TRUE.

Red black trees are also balanced binary search tree not just AVL
But that is not the part of GATE Syllabus, so it makes AVL the default Balanced Balanced Binary Search Tree.

## worst case for Balanced Binary Search Tree = $O(logn)$

### Subscribe to GO Classes for GATE CSE 2022

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$
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.
@tariq husainkhan plz tell me as they mention that it is balanced binary tree means they want to merge the concept of avl and bst
Balance binary search tree time complexity is always (logn).
edited
@swami patel height balanced binary search tree also known as AVL tree.

### In general $\Theta ( f(n) + g(n) ) = max(f(n), g(n))$ hence $\Theta ( logn + n ) = max(logn, n) = n$

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)