Search in a skip list at O(logk)

In summary, the conversation is about finding an element x in a skip list and implementing it in O(logk) expected running time, where k is the location of x in the list. The person understands how to do it in O(logn) but not O(logk). They are asking for a general description or pseudo code to find a reasonable upper bound on the position of the element in O(logk) time.
  • #1
Edd257
5
0
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.
 
Physics news on Phys.org
  • #2
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.
 

Related to Search in a skip list at O(logk)

1. How does searching in a skip list have a time complexity of O(logk)?

The time complexity of searching in a skip list is determined by the number of levels in the list. Each level has half the number of nodes compared to the level below it, resulting in a logarithmic pattern. This means that as the size of the skip list increases, the time it takes to search it only increases logarithmically.

2. How does a skip list differ from a regular linked list when it comes to searching?

In a regular linked list, searching for a specific element requires traversing through each node sequentially. However, in a skip list, we can use the "skip" pointers to quickly move to the next relevant node, reducing the time complexity to O(logk).

3. Can a skip list have multiple elements with the same value?

Yes, a skip list can have multiple elements with the same value. This is because each level of the skip list is essentially a separate linked list, allowing for duplicate values to be stored at different levels.

4. What happens if an element is inserted or removed in a skip list?

Inserting or removing an element in a skip list requires updating the "skip" pointers to maintain the skip list's structure. This operation has a time complexity of O(logk), similar to searching.

5. How does the space complexity of a skip list compare to other data structures?

The space complexity of a skip list is O(n), where n is the number of elements in the list. This is similar to a regular linked list. However, compared to other data structures such as a balanced binary search tree, the space complexity of a skip list is generally higher.

Similar threads

Comp Sci Implementing a PriorityQueue w/ a Doubly-Linked List (Java)
    • Engineering and Comp Sci Homework Help
Replies
2
Views
3K
Engineering Current density calculation in anisotropic ferromagnetic film
    • Engineering and Comp Sci Homework Help
Replies
7
Views
829
I Runge-Kutta 4 w/ some sugar on the top: How to do error approximation?
    • Differential Equations
2
Replies
61
Views
1K
Winning Lines for Tic-Tac-Toe (C programming)
    • Engineering and Comp Sci Homework Help
Replies
5
Views
5K
Dynamic allocation of adjacency matrix and traversing a list
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Creating Search Queries using indents
    • Programming and Computer Science
Replies
8
Views
941
Finding the position of a differential drive robot
    • Engineering and Comp Sci Homework Help
Replies
9
Views
2K
I don't understand kind of program the instructions want
    • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
Challenge: Find the minimum amount of draws possible for a list of integers
    • Programming and Computer Science
Replies
9
Views
1K
Java FileFinder using Breadth First Search algorithm fails
    • Programming and Computer Science
Replies
2
Views
716

Hot Threads

Recent Insights

Back
Top