Skip List randomization complexity
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)$.