29 votes 29 votes The recurrence relation that arises in relation with the complexity of binary search is: $T(n) = 2T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$ $T(n) = T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$ $T(n) = T\left(\frac{n}{2}\right)+\log n$ $T(n) = T\left(\frac{n}{2}\right)+n$ Algorithms gate1994 algorithms recurrence-relation easy isro2017 + – Kathleen asked Oct 4, 2014 • recategorized Apr 25, 2021 by Lakshman Bhaiya Kathleen 18.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 44 votes 44 votes Correct Option: B Searching for only one half of the list. leading to $T(n/2) +$ constant time in comparing and finding mid element. Gate Keeda answered Oct 7, 2014 • edited May 12, 2021 by soujanyareddy13 Gate Keeda comment Share Follow See all 3 Comments See all 3 3 Comments reply srestha commented Sep 18, 2019 reply Follow Share Recurrences: https://stackoverflow.com/questions/14679790/solving-the-recurrence-tn-tn-2-lg-n https://stackoverflow.com/questions/10884303/recurrence-relation-tn-tn-2-n 1 votes 1 votes `JEET commented Jan 2, 2020 reply Follow Share For anyone thinking why its $\mathbf{T(n/2)}$ and not $\mathbf{2T(n/2)}$. So, the answer is we are dividing the answer into 2 parts and then searching in only $1$ part. 5 votes 5 votes Ritik gupta commented May 7, 2021 reply Follow Share we are not dividing into two parts we are always making here T($n$/$2$) means do input half everytime till you reach the base case or find the answer and as you know in array random access is there so we add 1 as a constant so T($n$)$=$T($n$$/$$2$)+$1$ .it is $not$ a $divide$ and $conquer$ $algorithm $ stackoverflow link 2 votes 2 votes Please log in or register to add a comment.
15 votes 15 votes option B is correct... akash.dinkar12 answered May 7, 2017 akash.dinkar12 comment Share Follow See all 10 Comments See all 10 10 Comments reply LavTheRawkstar commented May 7, 2017 reply Follow Share please tell this also dear respected sir https://gateoverflow.in/128484/solve-using-recursion-tree-method-when-both-parts-are-unequal 0 votes 0 votes shraddha_gami commented May 7, 2017 reply Follow Share https://gateoverflow.in/2444/gate1994_1-7 i selected option A and worst case to search in BST is O(n) Option B is may be for balanced BST 1 votes 1 votes akash.dinkar12 commented May 7, 2017 reply Follow Share any issues Shraddha??? 0 votes 0 votes shraddha_gami commented May 7, 2017 reply Follow Share @akash worst case for BST is O(n) 0 votes 0 votes akash.dinkar12 commented May 7, 2017 reply Follow Share I think, u are not reading question carefully. They are asking about Binary Search algorithm which is used in searching of elements in ordered lists.. 1 votes 1 votes shraddha_gami commented May 7, 2017 i edited by shraddha_gami May 7, 2017 reply Follow Share Yeah! i know that what if tree is ordered and only one sided like this 0 votes 0 votes papesh commented May 7, 2017 reply Follow Share @shraddha_gami The question is about binary search not for binary search tree . hope u get the point ?? 3 votes 3 votes shraddha_gami commented May 8, 2017 reply Follow Share @papesh Still I didn't get that It is not always possible that we start search from middle element. And the concepts are related to each other that's the reason I shown the BST. It is Gate 1994 question https://gateoverflow.in/2444/gate1994_1-7 And answer is Option A 0 votes 0 votes Sandeep Suri commented Jan 9, 2018 reply Follow Share They are asking about Binary search that is when array is already sorted with distinct element we can directly jump to middle and after comparing middle we can either go peft or go right we have to follow one path.. Ie T(n2) + k 1 votes 1 votes Shubham Aggarwal commented Nov 8, 2018 reply Follow Share it seems easy by using master theoram. 0 votes 0 votes Please log in or register to add a comment.
13 votes 13 votes (b) T(n)= T(n / 2)+ k , where k is constant http://www.geeksforgeeks.org/binary-search/ anonymous answered May 7, 2017 anonymous comment Share Follow See all 0 reply Please log in or register to add a comment.
11 votes 11 votes answer is B in binary search once checked with middle value. we need to do the operation only with one half of the array. Sankaranarayanan P.N answered Oct 9, 2014 Sankaranarayanan P.N comment Share Follow See 1 comment See all 1 1 comment reply Divyanshum29 commented Sep 29, 2018 reply Follow Share sir, it means we always apply operation in the tree with in-order traversal because in-order is sorted if elements in the list are 3,7,1,2,9 and they are asking to form a binary tree then we will first sort it in ascending order and then form a tree? but I think we make a tree with 3 as a parent and then right is 7 then left of 3 is 1 like this? A BIG confusion arises 0 votes 0 votes Please log in or register to add a comment.