Test series

Question

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?

• A. $T(n) = T(n/2) + 1$
• B. $T(n) = 2T(n/2) + 1$
• C. $T(n) = T(n/3) + 1$
• D. $T(n) = 2T(n/3) + 1$

Comments

based on recursion tree depth C is the most suitable answer.

---

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.

---

$T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+1$

---

in option c we get unbalanced levels in recursion tree so option may be c

Answer 1

recurrence relation should be in worst case

T(n)=T(2n/3)+1

Answer 2

by taking approximation it will be option D