Skip lists with limited height

Question

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?

Answer 1

Hint: If the height is $k$, then the search complexity should be $O(kn^{1/k})$ (so the best choice is $k = \log n$, giving logarithmic time). Each level should contain every $n^{1/k}$th element of the lower level. Do the obvious thing - find the two elements bracketing your element in the first level, then the two elements bracketing it in the second level, and so on.