Scan every *i*th entry of L for a fixed i.
Suppose you have established that

then sequentially search .

because there are partitions, and there are (*i*-1)
items to search sequentially within a partition.

eg. *i*=4, *W*(*n*)=*n*/4+3

*i*=10,*W*(*n*)=*n*/10+9

*i*=100,*W*(*n*)=*n*/100+99

but still *O*(*n*) for fixed *i*.

How about *i* depending *n*?

eg.

better than *O*(*n*) of seq search.

( )

eg.

better than .

eg.

Let us minimize for *i*,

*W*(*n*)=*n*/*i*+*i*-1

set to 0 and solve, gives .

Hence is the best
possible with the approach.

Thu May 13 13:13:06 EDT 1999