Question

To which datastructure are skip lists similar to in terms of time complexities in worst and best cases?

(a) balanced binary search trees

(b) binary search trees

(c) binary trees

(d) linked lists

The doubt is from Skip List in chapter Types of Lists of Data Structures & Algorithms I

This question was posed to me during a job interview.

Answer 1

Correct answer is (a) balanced binary search trees

The explanation is: Skip lists are similar to any randomly built binary search tree. a BST is balanced because to avoid skew tree formations in case of sequential input and hence achieve O(logn) in all 3 cases. now skip lists can gurantee that O(logn) complexity for any input.