What is the expected time complexity to search for an element in a skip list compared to a standard singly linked list?

• A. Skip list search is O(n) on average; standard singly linked list search is O(n).
• B. Skip list search is O(1); singly linked list is O(n).
• C. Skip list search is O(log n) on average; standard singly linked list search is O(n).
• D. Skip list search is O(log n) worst-case; singly linked list is O(1).

Answer: (C)

Skip lists get their speed by using several levels of forward pointers, so you can skip over many elements at once. As you search, you move forward on higher levels and drop down as needed, and the number of steps you take grows with the height of the structure. Because the height grows only about as log n, the average case for searching is O(log n). A standard singly linked list has no higher levels to skip, so you must check elements one by one from the start, giving O(n) time on average. So the best description is that a skip list search is O(log n) on average while a singly linked list search is O(n). (Note: the skip list can be O(n) in the worst case, but the average case is O(log n).)