The time complexity of search operations in a Skip List is O(log n) on average. This average-case time complexity is achieved due to the use of multiple levels and express lanes that allow the algorithm to skip over large portions of the list during the search.
Here's a brief overview of how the search operation works in a Skip List:
-
Start at the Top:
- Begin the search at the top-left corner of the Skip List (highest level).
-
Move Diagonally:
- Move diagonally down and right until finding an element greater than or equal to the target.
- When moving to the next level, skip elements that are less than the target.
-
Repeat or Terminate:
- Repeat the process on each level until reaching the bottom level or finding the target.
The use of express lanes, which are created by having multiple levels in the Skip List, allows the search to skip over elements efficiently, leading to the logarithmic time complexity.
It's important to note that the O(log n) average-case time complexity assumes a balanced distribution of elements across levels. The randomness in assigning levels during insertion helps maintain this balanced structure on average. In the worst case, the time complexity for search operations is O(n), but this is highly unlikely in practice due to the random level assignment.
