So I have seen this question about probabilistic skip list space consumption: (answer)
but I think that the asker wasn't clear if he wanted an expected approach or the worst case approach.
So I would like to raise this question into a debate again and I will explain why I'm confused.
To be clear - I'm looking for the space complexity of a probabilistic skip list in the worst case. This is what I had in mind:
On one hand, we assume that the maximum levels number is log(n) it's easy to infer that in the worst case we might have n nodes in each level which will give us O(nlogn). On the other hand, I assume that there might be more than log(n) levels (e.g lists) and we set that bound to be n - then we get nn => O(n^2)
BUT! I don't understand why we have the right to limit the levels, if a new level depends on the coin toss, let's assume that in the worst case we will get infinte times Heads (which means a new level) and then we difer that it's not even bounded?! I'm confused.
If you don't set an upper bound on the height of the skip list, then there is no upper-bound to the worst-case space usage. For any bound you could place, there's some horribly unlucky and astronomically improbable execution of the skiplist that would result in a number of layers so high that the upper bound wouldn't hold. For this reason, in this case there isn't an upper bound on the space usage.
That said, most standard skiplist implementations place some upper bound M on the height of each node, usually chosen so that M is going to be bigger than log n. In that case, the worst-case space usage would be Θ(Mn), which happens if every mode uses all M levels
Hope this helps!