0

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

enter image description here

And in general:

enter image description here

Dan
  • 23
  • 5
  • 2
    Does this answer your question? [Show that the summation ∑ i to n (logi) is O(nlogn)](https://stackoverflow.com/questions/21152609/show-that-the-summation-%e2%88%91-i-to-n-logi-is-onlogn) – Raymond Chen Sep 14 '21 at 14:22
  • @RaymondChen not the same as my problem, we don' add log(i) for every i... – Dan Sep 14 '21 at 14:23
  • notice at first we added only 1 then second we added only 1 then 2. it is smaller that sum of log(i) so those are totally different problems – Dan Sep 14 '21 at 14:23
  • 2
    Your formula `S(n) = S(n-1) + log(n)` simplifies to `S(n) = sum(log(i), i = 1..n)` – Raymond Chen Sep 14 '21 at 14:25
  • But I said it's wrong... :) that was just my wrong try @RaymondChen – Dan Sep 14 '21 at 14:35
  • can someone help with this? – Dan Sep 14 '21 at 14:44
  • I'm not sure I understand what `Claiming that worst space complexity is nlog(n) isn't accurate since n changes from run to another` means-- n is a variable, usually taken to be the current number of elements in the list. At any point in time, if n is the current number of elements, the space used is at most O(n log n). The fact that the value of `n` is changing isn't relevant; just replace it with 'Current Cardinality' if you prefer – kcsquared Sep 14 '21 at 14:46
  • @kcsquared others claimed it can reach nlog(n) since each element can be added log(n) times at maximum. that is wrong, each element is added log(n) times for the n that was there when the elements was being added not the final n so you can't simply multiply. – Dan Sep 14 '21 at 14:48
  • 1
    The inconsistent terminology is creating confusion. Usually a "node" is a single element, of variable "height". You seem to be using the term "node" to mean "pointer" (so an element of height 5 consumes 5 "nodes"). You say "maximum height is log(n) where n is the number of leafs in the list", but then your formula treats `n` as the number of nodes, not the number of leafs. – Raymond Chen Sep 14 '21 at 16:35

0 Answers0