Test Series

Question

Comments

https://classes.soe.ucsc.edu/cmps102/Fall01/solutions4.pdf

---

The answer given is Option(D).

I think there is mistake in options.

---

The test-series is not having a name?

Answer 1

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

Answer 2

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

Comments

@dharmendra

Can you please explain in detail

I'm not able to understand the solution.

Thanks

---

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