Proving a recursive algorithm on a set is true

Question

If I have an algorithm that returns the entry of a set with the largest value, how do I prove the algorithm is true mathematically? (I know I could just write tests for it.) I understand how to use mathematical induction to prove a recursive algorithm over a linear recurrence relation or a sequence.

I think the difference that I am having difficulty with is an inductive proof of a sequence or equation deals with scalar variables, while an algorithm that returns the entry of a set with the largest value deals with set variables with multiple entries and of arbitrary length.

Here is the simple algorithm in pseudocode, in case it helps any kind person who helps me with this:

function maximum(Set s) {
  if (s.length == 0) {
    return null;
  } else if (s.length == 1) {
    return s[0];
  } else if (s[0] > s[s.length - 1]) {
    s = s.removeLast();
    return maximum(s);
  } else {
    s = s.removeFirst();
    return maximum(s);
  }
}

Let removeFirst and removeLast return a new view on the set, so the original set is not chopped up.

So, I don't know how to apply induction to this or whether I should use some other method.

Thanks in advance for any help.

Chris

Answer 1

I suppose you can prove that the algorithm returns the correct answer for any input set of size $1$.

Let's suppose that you have proved that the algorithm returns the correct answer for any input set of size $n-1$. Then, given a size $n$ set, either the first element is greater than the last, or not. If it is, the greatest element is not the last, so it must be within the first $n-1$ elements, and hence is equal to maximum(s.removeLast()) (because we know that any $n-1$-sized set t has maximum equal to maximum(t)).

Again, if the first element is not greater than the last, then the maximum element must be within the last $n-1$ elements, and hence is equal to maximum(s.removeFirst()).