Quote:

I need to prove by induction;

j-i < 2^n => A(i, j) =< n

for any random table T with N entries.

for every number i,j,n where 1=< i =< j =< N and n >= 0.

1. You have not defined A(i, j). I assume it is the number of recursive calls in FindZero(i, j).

2. I suspect that even though T is random, it must be ordered.

3. I also suspect that N and n are the same object.

Quote:

My basisstep is P(0)

j-i < 1 => A(i,j) =< 0

This is what you need to show. Is this indeed true?

Quote:

I want to prove p(n) is true and by that I show that p(n+1) is true.

No, you *assume* that P(n) is true and from there you show P(n+1). When you assume, it's like you are payed and you can spend this sum on buying P(n+1); when you prove, it is similar to paying. Also, p and P should not be confused. Finally, it's a good idea to write P(n) (not P(0) or any other special case) explicitly in the beginning. First, this serves to define the letter P (and every object must be properly introduced), and, second, this help eliminate errors when one writes P(n+1).

Quote:

So I need to prove

j-i < 2^(n+1) => A(i,j) =< n+1

My feeling is that I have to show that both j-i < 2^(n+1) is true and A(i,j) =< n+1 is true.

Again, you *assume* j-i < 2^(n+1); this is given to you for free. From here, you have to show A(i,j) =< n+1. It's also a good idea to write the induction hypothesis (IH): j-i < 2^n => A(i, j) =< n, which is also given for free.

To show A(i, j) =< n + 1, we look at the algorithm. If i = j, then A(i, j) = 0 <= n + 1. Suppose i <> j. Then we have $\displaystyle k=i+\lfloor (j-i)/2\rfloor$ and at least one recursive call: either A(i, k) or A(k + 1, j). Thus, either A(i, j) = A(i, k) + 1 or A(i, j) = A(k + 1, j) + 1. We could use the IH if we showed that k - i < 2^n *and* j - (k + 1) < 2^n; this would give us that A(i, k) < n and A(k + 1, j) < n, so in either case we have A(i, j) < n + 1. So, we are left to prove that k - i < 2^n and j - (k + 1) < 2^n.

The first of these inequalities is easier, so let me make a couple of remarks about the second one. It is pretty easy but requires accuracy in finding upper and lower bounds. This skill is very important for the analysis of algorithms.

We have j - k - 1 < 2^n iff j - k <= 2^n since both sides are integers. Next, $\displaystyle j - k = j - i - \lfloor (j-i)/2\rfloor$. To find an upper bound (hopefully, 2^n) for this, we have to find a *lower* bound for $\displaystyle \lfloor (j-i)/2\rfloor$. (Recall that for any a, b and b', a - b <= a - b' iff b >=b', i.e., the inequality is reversed.) You could use the fact that $\displaystyle \lfloor (j-i)/2\rfloor\ge (j-i)/2-1$ (in fact, strict inequality holds). Make sure you understand why this is the case and try to finish the proof.