Search in a skip list at O(logk)

[Edd257]

I need to write a code that finds element x in a skip list. I need to implement that in O(logk) expected running time, where k is the location of x at the list (i.e., there are k-1 elements before x in the list).

I know how to do it at o(logn), but not o(logk).

can you show me the way? I need only general description or pseudo code, not more than that.

 

[mfb]

Can you find a "reasonable"* upper bound on the position of your element that runs in O(logk)?

*n is a trivial upper bound of course and does not help, the only non-trivial way I see is reasonable.