the time complexity of Skip List

algorithm data-structures skip-lists
user1487718 picture user1487718 · Oct 4, 2012 · Viewed 12.3k times · Source

May I know why the time complexity of insertion of skip list is O(log n) for average case, and why the height of Skip list with n elements is O(log n) in high probability. And why average search time in each layer is O(1).

Answer

grid picture grid · Oct 4, 2012

I can help with the O(log n) part.

Basically... [Skip list searching] is quite reminiscent of binary search in an array and is perhaps the best way to intuitively understand why the maximum number of nodes visited in this list is in .

Related questions

Skip List vs. Binary Search Tree

I recently came across the data structure known as a skip list. It seems to have very similar behavior to a binary search tree. Why would you ever want to use a skip list over a binary search tree?

Read More
How to implement a queue using two stacks?

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

Read More
How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a …

Read More