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!

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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Search in a skip list at O(logk)
  1. Linux listing (Replies: 7)

  2. Searching on Fortran (Replies: 13)