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)