Insertion and removal time in a Skip List

Question

I am little confused on the time it takes to insert or remove an element from a skip list.

Lets say there is a skip list with height H and each level contains n/2^i entries.
n = total number of key value pairs
i = level of the skip list i<= H

Now, as per the theory an insertion operation will perform following actions
1. Find a key <= the key being inserted.
2. insert this key
3. randomly create this entry in the levels above the base level.

Lets assume the Skip list is based on a linked list.
Step 1: Should take O(n).
Step 2: Should be O(1).
Step 3: Should be O(log n) time. I am still confused in this logic and it will be part of the question below

Question

1. Based on the above facts shouldn't the time of insertion be O(n) + O(1) + O(log n)? ignoring the lower order terms its should go by O(n) + O(log n)?

2. Step 3 again should take O(n) time to search a key <= key being inserted and then o(1) to insert. Resulting in a much complex insertion running time?

Books say that insertion in a skip list takes O(log n) time. I must be missing some important piece of information, could you please help me get a good understanding of this concept.

Answer 1

The entire point of the skip list is to not have to run through the whole list to find an item. You search in the upper list first, then you go down one level and so on until you reach the base list.

Let's say the top list contains 2 items, the first one and one somewhere in the middle. When you search for your item, the list is already cut in half. Each level will approximately cut the list in half. This is what makes the insert O(log n).

Answer 2

As skip lists are used for storing sorted data, you can do something smarter than linear searching when looking for the position to insert a new element.

Basically, you can do something similar to binary search using the pointers in the higher levels. For example, by checking the link on the log n - 1th level, you can compare the new item to the item in the middle of the list, thus determining if it should be inserted in the first or second half of the list. You then continue like this, every time looking at the links at lower levels to gain better precision. This brings the complexity of Step 1 in your algorithm down to O(log n).