Scan every ith 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
but still O(n) for fixed i.
How about i depending n?
better than O(n) of seq search.
better than .
Let us minimize for i,
set to 0 and solve, gives .
Hence is the best possible with the approach.