Analysis of Skiplists
Explore the analysis of skiplists by understanding their expected height, size, and search path length through basic probability concepts. Learn how coin toss experiments model skiplist behaviors leading to efficient O(log n) search performance and linear size.
We'll cover the following...
We'll cover the following...
Here, we analyze the expected height, size, and length of the search path in a skiplist. This section requires a background in basic probability. Several proofs are based on the following basic observation about coin tosses.
Lemma 1: Let be the number of times a fair coin is tossed up to and including the first time the coin comes up heads. Then ...