# Skip List randomization complexity

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)$?

• 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!
– Raphael
Nov 2, 2016 at 7:59

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