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

1 Answer

+34 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 (332k points)
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.


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

32,544 questions
39,231 answers
109,310 comments
36,613 users