Selection , Finding the largest of a set with Ternary comparator.

Question

Let S be a set of n>0 distinct integers.Assume that n is a power of 3. A ternary comparison can compare three numbers from the set S and order them from the largest to the smallest.

Describe an efficient algorithm that uses as few as possible ternary comparisons to find the largest number in the set S.Explain why your algorithm is correct and state the exact number of ternary comparisons it uses in the worst case.

This was a mid term question.

My answer was as follows:

T(n) = 3T(n/3) + 1

resolves to (n/2) -1

Is there a more efficient way to do this ?

Thanks.

Answer 1

i don't think you can do better than that. note that each comparison lets you discard exactly two numbers from consideration. you should get (n-1)/2, not (n/2)-1 though.