1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Search in a skip list at O(logk)

  1. May 16, 2015 #1
    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.
  2. jcsd
  3. May 16, 2015 #2


    User Avatar
    2017 Award

    Staff: Mentor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted