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)$?
Skip List randomization complexity
algorithm analysis;data structures;runtime analysis;lists
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)$.