In skip lists:
- maximum height is log(n) where n is the number of leafs in the list.
- Thus, At worst every node is added log(n) times.
Claiming that worst space complexity is nlog(n) isn't accurate since n changes from run to another. So how can I proves nlog(n) is worst space complexity? and to be more specific I want to prove that worst space isn't O(n).
if we start with 1 node, then at max we can add log(1) which gives as 2 nodes. Then adding another node at max we can add log(2) which gives as 3 total nodes. Adding another one at max we can add log(3) -upper rounding- which gives as total 5 nodes.
The first few number of elements is (separated by commas):
And in general:
