[Solved] What is the time complexity improvement of skip lists from linked lists in insertion and deletion?

What is the time complexity improvement of skip lists from linked lists in insertion and deletion?

a) O(n) to O(logn) where n is the number of elements
b) O(n) to O(1) where n is the number of elements
c) no change
d) O(n) to O(n2) where n is the number of elements

Answer: a
Explanation: In Skip list, we skip some of the elements by adding more layers. In this, the skip list resembles balanced binary search trees. Thus we can change the time complexity from O (n) to O (logn)

Comments