This is homework, so please only hints. I didn't want to put this on StackOverflow since this is mostly about theory, and SO gets inundated with too many questions.I am asked to find a method of arranging items in a skiplist, with height limited to 3 and unlimited number of elements, in such a way such that searching takes worst-case $\Theta (n^{1/3})$. No restriction on how expensive the arranging part is; just describe what subset of the keys go into which level.I am somewhat confused. How can a skiplist with a limited number of items have search complexity anything other than $\Theta(n)$? Clearly, with any clever algorithm, I can just fill the skiplist with a horrendous amount of elements, and as the number of elements goes up, surely the handicapped skiplist can't do any better than a linked list asymptotically? I think I can prove this for the simple set of rearranging algorithms that put a random proportion $q$ of the items into the second layer, and another random proportion $p$ of items within these items to the top layer.Am I missing anything obvious? Is the question faulty?
Skip lists with limited height
data structures;lists