in DS recategorized by
7,892 views
42 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)$
in DS recategorized by
by
7.9k views

4 Comments

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.

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

worst case for Binary Search Tree = $O(n)$

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

 

1

Subscribe to GO Classes for GATE CSE 2022

2 Answers

80 votes
 
Best answer
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
by

9 Comments

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

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

hence $\Theta ( logn + n ) = max(logn, n) = n$

0
4 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

Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true