1 votes 1 votes Consider the variation of the binary search algorithm so that it splits the list into not only into two sets of almost equal sizes but into two sets of size approximately one-thirds and Two-third. What is the recurrence equation for this search in worst-case? $T(n) = T(n/2) + 1$ $T(n) = 2T(n/2) + 1$ $T(n) = T(n/3) + 1$ $T(n) = 2T(n/3) + 1$ Algorithms algorithms recurrence-relation test-series + – Warrior asked Mar 6, 2018 • retagged Jul 16, 2022 by Anjana5051 Warrior 1.8k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Tesla! commented Mar 6, 2018 reply Follow Share based on recursion tree depth C is the most suitable answer. 0 votes 0 votes Akhilesh Singla commented Mar 7, 2018 reply Follow Share I think it should be D. Because in worst case we might keep on searching in the larger two-third part. C is more like the best case. 1 votes 1 votes Anand. commented Mar 7, 2018 reply Follow Share $T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+1$ 1 votes 1 votes G Shaheena commented Mar 25, 2018 reply Follow Share in option c we get unbalanced levels in recursion tree so option may be c 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes recurrence relation should be in worst case T(n)=T(2n/3)+1 abhishekmehta4u answered Mar 7, 2018 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes by taking approximation it will be option D BASANT KUMAR answered Mar 26, 2018 BASANT KUMAR comment Share Follow See all 0 reply Please log in or register to add a comment.
