Ternary Search Recurrence Relation I am trying to work out the recurrence relation for Ternary Search. This is what I came up with:

C(n) = C(n/3) + 2


However, I talked to my professor and he said it's not correct. He says that we need to take all of their cases into account. This part confuses me a little bit, can you please clear it for me?

Thank you.
Hint: Recall what you are actually doing in ternary search - you basically partition the list into 2 parts, on of roughly $n/3$ elements, and the other of $2n/3$ elements. 

So, on a bad day (worst case) you do $2n/3$ recursive calls. 

Then the recurrence relation is $$T(n) = T(2n/3) + c $$

I'll cheat a bit here and use the master theorem to jump to the conclusion that $T(n) \in \Theta(log\ n)$