i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is T(n/3)+c and T(2*n/3)+c. I want to know which one is correct as solution for both is same.

i have referred a and b and both are different. Which one is True and HOW???

Also the number of comparison in binary search is logn+1,So what is the number of comparisons in Ternary search and how?please elaborate it


You could do ternary search by splitting into three parts, use one comparison to see if the key has to be in the first third, and another one to distinguish between second and third stretch if it isn't in the first one. Assuming uniformly distributed searches, this would reduce the range to a third with $1/3 + 2 \cdot 2/3 = 5/3$ comparisons. This idea leads to $T(n) = T(n/3) + c$ (approximately).

Another idea would be to split in three, with one comparison check if it is in the first third, and continue recursively with the part containing the key. This leads to $T(n) = 1/3 T(n/3) + 2/3 T(2 n /3) + c$ (again a rough approximation to the real recurrence).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.