0 votes 0 votes Algorithms algorithms binary-search recurrence-relation ace-test-series + – ben10 asked Sep 9, 2018 retagged Jul 8, 2022 by Lakshman Bhaiya ben10 827 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Mk Utkarsh commented Jan 18, 2018 reply Follow Share https://classes.soe.ucsc.edu/cmps102/Fall01/solutions4.pdf 3 votes 3 votes ankit_thawal commented Jan 18, 2018 reply Follow Share The answer given is Option(D). I think there is mistake in options. 0 votes 0 votes Arjun commented Sep 9, 2018 reply Follow Share The test-series is not having a name? 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes Binary search will devide the element into two parts and after that it will go either left or right..but in this question it is divided into 1/3 and 2/3..so after finding middle element we have two choice either to go for 1/3 element or 2/ 3 element.. But in this question worst case is asked so it will go for 2/3 element..so finally T(n)=T(2n/3)+ c Sushant kaushal answered Jun 5, 2018 Sushant kaushal comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Search dividing array into two parts n/3 and 2n/3 out of these it will select one part , where it have to make again search so in worst case recurrence relation will be T(n)= T(2n/3)+1 or T(n)= T(n/3)+1 so I think answer should be C Dharmendra Lodhi answered Sep 9, 2018 Dharmendra Lodhi comment Share Follow See all 2 Comments See all 2 2 Comments reply Mayankprakash commented Sep 10, 2018 reply Follow Share @dharmendra Can you please explain in detail I'm not able to understand the solution. Thanks 0 votes 0 votes Dharmendra Lodhi commented Sep 10, 2018 reply Follow Share modified binary search algo dividing array in two parts n/3 and 2n/3 so in worst case it may select 2n/3 so not it recursively search in that 2n/3 array only . so recurrence relation will be T(n)= T(2n/3)+1 and if it is selecting n/3 part of array then recurrence relation will be T(n)= T(n/3)+1 1 votes 1 votes Please log in or register to add a comment.