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

• Does it matter what c is? Or is c 5? – Julio Garcia Oct 7 '13 at 2:45
• In case $T(n)$ measures the running time, a constant like $5$ is meaningless, since the running time depends on the exact model of computation, and we don't want to worry about such details. Rather, we take $c = O(1)$. (When $T(n)$ counts the number of comparisons, for example, an exact value for $c$ does make sense.) – Yuval Filmus Oct 7 '13 at 4:02
• Ah, now it makes sense. Thanks, you two! – Julio Garcia Oct 7 '13 at 4:23

Ternary search (a)-> If you divide the array into 3 subsets of equal size and consider 3 cases key lies in left,middle, right tree, Then the recurrence : T(n)=T(n/3)+O(1) must be correct, because you are searching in an array of size(n/3).

Ternary search (b)-> If partitioned in size (n/3) and (2n/3) 2 partitions then the recurrence T(n)=T(2n/3)+O(1) holds.

Both are different variations of ternary search

• Could you please elaborate or be clearer? a is the number of problems that need to be solved, b shows how the array is split up, and c is the time spent on ops. – Debosmit Ray Mar 17 '16 at 8:26