Recall the skip list data structures we introduced in class

Recall the skip list data structures we introduced in class where concept of randomization is introduced.Now we consider a deterministic version and suppose that we use only two levels, i.e., two linked lists, for n elements. Each element is in linked list S0 and some elements are also in the other linked list S1. Please show that the search cost can be minimized to O(sqrt(n))

Solution

In Skip List with 2 List can be considered as above list as Express Lane and below list as normal Lane.Time complexity in this is number of nodes on express lane and number of nodes in a segment of normal lane.Here Segment can be defined as number normal lane nodes between 2 express lane nodes.Hence there n nodes in normal lanes  and n nodes on express lane.When we equally divide the normal lane , then there will be n nodes in every segment of normal lane.Hence number of nodes traverse for each search will be n.Hence time complexity will be O(n)