N is Z loadet in a table T in the spots 1,2,...,N, arranged so that the number in spotialways is smaller og equal to the number on the spoti+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:

$\displaystyle j-i < 2^n \Rightarrow A(i,j) \leq n$

for every Z i,j,n with $\displaystyle 1\leq i \leq j \leq N and n \geq n$