Skip List randomization complexity

Question

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