CODEWITHSUNDEEP
algorithmdata-structuresskip-lists
user1487718
user1487718

Reputation:

the time complexity of Skip List

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).

Upvotes: 3

Views: 17714

Answers (1)

grid
grid

Reputation: 323

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 .

Upvotes: 3

Related Questions