Bumping this thread, as I have modified a bit in the text.
N is Z loadet in a table T in the spots 1,2,...,N, arranged so that the number in spot i always is smaller og equal to the number on the spot i+1.
Example given.
-1212 | -1002 | -800 | -545 | -123 | -54 | -2 | 0 | 4 | 321 | 324 | 501
(N = 12), We wish to determine wether 0 is part of this table og look at the following algorithm.
Psedu code picture by krakatau7 - Photobucket
Question (B)
Consider a random arranged table T with N entries (inputs?). Prove by induction this claim:
for every Z i,j,n with
furthermore
we assume P(n) j-i < 2^n => A(j,i) n
is TRUE
and now we want to prove P(n+1) is true
P(n+1) j-i < 2^n+1 => A(j,i) n+1
if we want to prove this, we need to show that
A(j,i) n+1
to prove this our teacher said we could use j' - i' < 2^n+1
and remake 2^n+1 into 2^n *2
I understand the rule of operation, but I dont see how this can help us to reach further in the induction.