The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
1.8k 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)$
asked in DS by Boss (17.8k points)
recategorized by | 1.8k views

1 Answer

+42 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)$
answered by Veteran (339k points)
edited by
+1
sir ,but in case of skewed bst height will be n.2^n then the tn=n.2^n
+7
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
+5
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).


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

34,781 questions
41,758 answers
118,936 comments
41,400 users