This is homework, so please only hints. I didn\'t want to put this on StackOverf

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 ?(n1/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 ?(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?

Explanation / Answer

Hint: If the height is k, then the search complexity should be O(kn1/k) (so the best choice is k=logn, giving logarithmic time). Each level should contain every n1/kth 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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects