Skip lists for probabilistic search in Data Structures Theory - Time & Space Complexity

Time Complexity: Skip lists for probabilistic search

O(log n)

Understanding Time Complexity

Skip lists use multiple layers of linked lists to speed up search operations.

We want to understand how the search time grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of searching for a value in a skip list.

function skipListSearch(head, target) {
  let current = head;
  for (let level = current.level - 1; level >= 0; level--) {
    while (current.next[level] && current.next[level].value < target) {
      current = current.next[level];
    }
  }
  current = current.next[0];
  if (current && current.value === target) return current;
  return null;
}
    

This code searches for a target value by moving forward on higher levels and dropping down levels when needed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Moving forward through nodes at each level.
• How many times: At most, it moves forward a few times per level, and there are about log(n) levels.

How Execution Grows With Input

As the list grows, the number of levels grows roughly with the logarithm of the size.

Input Size (n)	Approx. Operations
10	About 3 to 4 steps
100	About 6 to 7 steps
1000	About 9 to 10 steps

Pattern observation: The steps increase slowly, roughly adding one step each time the input size multiplies by 2 or more.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly and efficiently even as the list gets very large.

Common Mistake

[X] Wrong: "Skip list search is as slow as scanning the whole list, so it is O(n)."

[OK] Correct: The multiple levels let the search jump ahead quickly, so it does not check every element one by one.

Interview Connect

Understanding skip lists shows you how clever data structures use randomness and layers to speed up search.

This skill helps you think about balancing speed and simplicity in real-world problems.

Self-Check

"What if the probability of adding a new level to a node changes? How would that affect the search time complexity?"