Prooving by induction that a function gets called n-1 times

Question

This is the pseudo-code from the problem:

Procedure Foo(A,f,L), precondition:

• A[f..L] is an array of integers
• f,L, are two naturals >=1 with f<=L.

Code

procedure Foo(A,f,L
    if (f=L) then

      return A[f]

    else

       m <-- [(f+L)/2]

       return min(Foo(A,f,m), Foo(A, m+1,L))

    end if

The Question:

Using induction, argue that Foo invokes min at most n-1 times.

I am a little lost on how to continue my proof for part (iii). I have the claim written out as well as the base case. Which i believe it to be n>=2. But how do I do it for k + 1 terms? Since this is a proof by induction.

Thanks

Answer 1

We will proceed by induction on n = L - f + 1.

Base case: when n = 1, f=L and we immediately return A[f] calling min zero times; we have n - 1 = 1 - 1 = 0.

Induction hypothesis: assume that the claim is true for all n up to and including k - 1.

Induction step: we must show the claim is true for k. Since L > f we execute the second branch which calls min once, and invokes Foo on subarrays of sizes floor(k/2) and ceiling(k/2).

• if k is even, k/2 is an integer and floor(k/2) = ceiling(k/2) = k/2. Both of these are less than k and so we know that Foo invokes min at least k/2 - 1 times for each call. But 2(k/2 - 1) + 1 = k - 2 + 1 = k - 1, so the minimum number of invocations must be k - 1 for n = k.
• if k is odd, k/2 is not an integer and floor(k/2) = ceiling(k/2) - 1. For k > 1, both of these are less than k and so we know that each recursive call invokes min at least floor(k/2) - 1 and ceiling(k/2) - 1 times, respectively. But floor(k/2) - 1 + ceiling(k/2) - 1 + 1 = floor(k/2) - 1 + floor(k/2) + 1 = 2*floor(k/2) - 1 + 1 = 2*floor(k/2). Since k is an odd integer, k/2 can be written w+1/2 where w = floor(k/2). Rearranging, we have that k = 2w + 1 and we invoke min at least 2*w times. But k - 1 = 2*w + 1 - 1 = 2*w = 2*floor(k/2), as required

Since k is either even or odd, and we have shown that in both cases the minimum number of invocations of min is at least k - 1, this completes the proof.