The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+25 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)$
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) $

answered by Veteran (339k 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.
@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).

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
41,400 users