Expected search complexity of a randomized skip list

A skip list assigns each inserted node a random height using independent coin flips with promotion probability p = 1/2 (a node reaches level k with probability (1/2)^k). No rebalancing of any kind is ever performed. What is the expected time to search for a key among n elements?

6 of 46 in Data Structures & Algorithms