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

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

StackExchange Computer Science Q#65410, answer score: 10