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.5k 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 Show 10 previous comments 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.