3
$\begingroup$

I understand the basics of Skip Lists and their implementation also the basic Search Insert Delete functions and their run time complexity. Recently after a lecture, a professor proposed an interesting question. He asked what we suspected the total time building a skip list using randomization.

A few hints were given:

  • $n \times (1/2 + 1/4 + \dots + 1/2^{k})$.
  • I understand this as, For every level of the skip list their is said to be half the nodes working from bottom level to the next one above it.
  • Using a geometric equation we came up with this formula: $n \times \frac{1/2^{k+1} - 1/2}{1/2 - 1}$

So ultimately what is the time complexity? $\Theta(n^2)$?

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 2 '16 at 7:59
9
$\begingroup$

According to the hint, the number of elements in the levels beyond the first is expected to be $$ n \cdot (1/2 + 1/4 + \cdots + 1/2^k). $$ Presumably, $k \approx \log n$, though as we will see, this doesn't really matter.

Let's plug in some numbers to see how this behaves. When $n = 100$ and $k = 10$, we get $$ 100 \cdot (1/2 + 1/4 + \cdots + 1/2^{10}) \approx 99.9. $$ When $n = 1000$ and $k = 15$, we get $$ 1000 \cdot (1/2 + 1/4 + \cdots + 1/2^{15}) \approx 999.97. $$ When $n = 10000$ and $k = 20$, we get $$ 10000 \cdot (1/2 + 1/4 + \cdots + 1/2^{20}) \approx 9999.99. $$ What is happening here? Massaging the formula for the sum of the geometric series, we get $$ n (1/2 + 1/4 + \cdots + 1/2^k) = n (1 - 1/2^k). $$ So as $k$ gets larger, the value of this formula gets closer and closer to $n$. Moreover, if $k \geq 1$ (say), then $$ \frac{n}{2} \leq n (1/2 + 1/4 + \cdots + 1/2^k) \leq n. $$ So from the point of view of asymptotic analysis, this expression is $\Theta(n)$ rather than $\Theta(n^2)$.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. Exactly what I was looking for. As far a as a visual example so to speak, let's say there's 8 nodes sorted at the base level, instead of being staggered all the nodes for the next 3 levels, assuming the next level(s) decreases by half the number of nodes in the previous level, the nodes are all stacked to one side. This can be the worst case of a "perfect" skip list expressed with complexity O(n), correct? $\endgroup$ – DJ2 Nov 4 '16 at 1:17
  • $\begingroup$ This is a "representative" case. $\endgroup$ – Yuval Filmus Nov 4 '16 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.