Medium
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