Recurrence Equations

Question

Given a problem, how to come up with a recurrence equation?

For example : 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.

This is one of the midterm question I had. I come up with

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

and other students come up with something else.

In general what to look for while finding a recursion for a problem?

Answer 1

It depends on the problem, but in general try to split the problem up into a smaller problem plus one more step, or several smaller problems, and a step that combines them.

I think your answer is right. How did you get to the answer? Can you explain the process you followed?

Here's how I would do it:

You can split the problem by partitioning the integers into three smaller, equally sized groups. Assume you know how to find the maximum of each smaller group in T(n/3), and then using your ternary comparison operator to find the maximum of the three maximums in one extra step (giving the +1). This is then the overall maximum. This gives the recurrence relationship you described. You also need to define the base case: T(1) = 0 or T(3) = 1. This doesn't prove that it is optimal, but I think you can prove that it is using a different argument.

Most recursive solutions follow similar patterns but there is no hard and fast rule you can always follow. Just practice on many different examples until you get the hang of it.