algorithmtime-complexitybig-ospace-complexityskip-lists

Space Complexity of Skip List is Wrong?

Wikipedia: https://en.wikipedia.org/wiki/Skip_list says that worst space complexity of skip list is O(n log(n)) but I don't agree at all.

Here is my proof:

Each time a skip list has at maximum log(n) layers, so each new node can be inserted at most log(n) times. If we start from a skip list with 1 node then this is how the total number of nodes grows:

enter image description here

In other words, the total sum after $n$ insertions is:

enter image description here

Which is much greater than O(n log(n))... (I just proved that S(n)=w(n^2) which is a contradiction).

Solution

  • Your confusion is summing twice.

    First, you say the total number of nodes (and not new nodes) is 1->2->3->5->8->... - and then you sum these numbers.

    But, the total number of nodes for n elements is the element in the series with index n, not the summation of all elements up to n.