If we apply partitioning recursively in the sublist, we get
for k partitions and each partition of size n/k.
Since, in order to identify a partition, we need not compare x with
L[1],
Say k=4, then
How large can i be?
Eventually, partition size will become equal to 1, when
or 
Then W(1)=1
Thus,
- much better than 
.
In general, for any fixed k,
