Ternary Search Recurrence Relation

Problem Detail: 

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.

Asked By : Julio Garcia

Answered By : Subhayan

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)$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14869