4k 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)$
in DS
recategorized | 4k views
0

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.

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

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)