2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Does it matter what c is? Or is c 5? $\endgroup$ – Julio Garcia Oct 7 '13 at 2:45
  • 2
    $\begingroup$ 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.) $\endgroup$ – Yuval Filmus Oct 7 '13 at 4:02
  • $\begingroup$ Ah, now it makes sense. Thanks, you two! $\endgroup$ – Julio Garcia Oct 7 '13 at 4:23
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Debosmit Ray Mar 17 '16 at 8:26

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.