30 votes 30 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.
16 votes 16 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 Show 7 previous comments 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.