CODEWITHSUNDEEP
algorithmtime-complexitybig-ospace-complexityskip-lists
rolen
rolen

Reputation: 47

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

Upvotes: 0

Views: 320

Answers (1)

amit
amit

Reputation: 178481

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.

Upvotes: 2

Related Questions