Proving 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.

   if (f=L) then
     return A[f]
   else
     m <-- [(f+L)/2]
     return min(Foo(A,f,m), Foo(A, m+1,L))
   endif

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\geq2$. But how do I do it for $k + 1$ terms? Since this is a proof by induction.

Thanks

Answer 1

Here, I'm going to let $n = L-f$ and let $M(f,L)$ be the number of times min is invoked when calling $Foo(A,f,l)$. Notice when $n=0$, then $L=f$ and clearly Foo invokes the function min $0$ times so the condition is satisfied.

Now suppose that the assertion is satisfied for $n \leq k$. We want to show it holds true for $n=k+1$, i.e., suppose that $L-f = k+1$. Since $Foo(A,f,L)$ has to invoke min once and then invoke it as many times as its invoked in the recursive calls, we get that,

$$M(f,L) = 1 + M(f,m)+M(m+1,L).$$

Now notice that for $M(f,m)$ and $M(m+1,L)$, the quantity $m-f$ and $L-(m+1)$ are both less than $L-f = k+1$ (since $m$ is essentially the midpoint of $L$ and $f$). So by the inductive hypothesis $Foo(A,f,m)$ invokes min at most $m-f-1$ times and $Foo(A,m+1,L)$ invokes min at most $L-(m+1)-1$ times. Plugging these into our equation yields, we get,

$$M(f,L) = 1 + M(f,m)+M(m+1,L) \leq 1 + (m-f-1) + (L-(m+1)-1) = L-f-1 = n-1,$$

as desired.