Question

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 number of elements

(b) O(n) to O(1) where n is number of elements

(c) no change

(d) O(n) to O(n^2) where n is number of elements

This interesting question is from Skip List topic in portion Types of Lists of Data Structures & Algorithms I

I got this question in homework.

Answer 1

The correct choice is (a) O(n) to O(logn) where n is number of elements

Easy 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)