50 votes 50 votes The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is $\Theta(n\log n)$ $\Theta(n2^n)$ $\Theta(n)$ $\Theta(\log n)$ DS gatecse-2012 data-structures normal binary-search-tree + – gatecse asked Aug 5, 2014 recategorized Jul 3, 2017 by Silpa gatecse 13.3k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply iwasifirshad commented May 3, 2020 reply Follow Share 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 votes 1 votes Neelam_$ingh_222 commented Jul 24, 2020 reply Follow Share Red black trees are also balanced binary search tree not just AVL 1 votes 1 votes Vishal_kumar98 commented Oct 24, 2020 reply Follow Share But that is not the part of GATE Syllabus, so it makes AVL the default Balanced Balanced Binary Search Tree. 2 votes 2 votes Raj Bopche commented Jan 26, 2021 reply Follow Share worst case for Binary Search Tree = $O(n)$ worst case for Balanced Binary Search Tree = $O(logn)$ 5 votes 5 votes Please log in or register to add a comment.
Best answer 92 votes 92 votes Balanced 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$ Arjun answered Aug 21, 2014 edited Jan 17 by shadymademe Arjun comment Share Follow See all 13 Comments See all 13 13 Comments reply Tariq Husain Khan commented Jan 19, 2015 reply Follow Share sir ,but in case of skewed bst height will be n.2^n then the tn=n.2^n 3 votes 3 votes Arjun commented Jan 19, 2015 reply Follow Share Yes. That's true. But here question specifies "balanced". 19 votes 19 votes Tariq Husain Khan commented Jan 19, 2015 reply Follow Share yeah sir i got it.. 1 votes 1 votes Regina Phalange commented Feb 28, 2017 reply Follow Share How binary search takes 0(logn) time in worst case?? it is 0(n). Someone please explain 0 votes 0 votes Tariq Husain Khan commented Feb 28, 2017 reply Follow Share 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 votes 10 votes Swami patil commented Mar 11, 2018 reply Follow Share @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 votes 0 votes abhishekmehta4u commented Mar 11, 2018 reply Follow Share Balance binary search tree time complexity is always (logn). 1 votes 1 votes talha hashim commented Aug 1, 2018 i edited by talha hashim Jan 11, 2020 reply Follow Share @swami patel height balanced binary search tree also known as AVL tree. 1 votes 1 votes Raj Bopche commented Jan 26, 2021 reply Follow Share In general $\Theta ( f(n) + g(n) ) = max(f(n), g(n))$ hence $\Theta ( logn + n ) = max(logn, n) = n$ 0 votes 0 votes Rutuja Desai commented Jan 26, 2022 reply Follow Share but isn’t it a fact that the time complexity class doesn’t change with the size of the input ? 0 votes 0 votes raja11sep commented Mar 19, 2022 reply Follow Share @Rutuja Desai but isn’t it a fact that the time complexity class doesn’t change with the size of the input? When the number of inputs = n, the time complexity of the linear search is O(n). When the number of inputs = n*n, the time complexity of the linear search is O(n*n). 0 votes 0 votes Rusty_01 commented Mar 26, 2022 reply Follow Share But if we have n^2 element binary search will still take (log n). Please tell me if this question is for heap then it would be log n or it will be n . I think it would be log n cause n elements would be on next just next level so it would not make any difference. 0 votes 0 votes Raj Bopche commented Apr 9, 2022 reply Follow Share For n^2 sorted elements, binary search will take log(n^2) time i.e $O(logn)$ time. 1 votes 1 votes Please log in or register to add a comment.
6 votes 6 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 n2n elements replace n2n in place of n Θ(log(n2n)) =Θ(logn+log2n) =Θ(logn+nlog2) =Θ(logn+n) =Θ(n) Mudrakola Karthik 3 answered Jun 12, 2018 Mudrakola Karthik 3 comment Share Follow See all 0 reply Please log in or register to add a comment.