- Forum
- General C++ Programming
- Analyzing Skip Lists
Analyzing Skip Lists
Hello all,
My question is on analyzing the time it takes to search for an element in a Skip List. As some may already know, searching for key k in a Skip List is done by a series of "drop down" and "scan forward" steps until the key with the largest value less than or equal to k is found . Below is an excerpt from my textbook (and is the source of my confusion):
"Let n(i) be the number of keys examined while scanning forward at level i. Observe that, after the key at the starting position, each additional key examined in a scan-forward at level i cannot also belong to level i + 1. If any of these keys were on the previous level, we would have encountered them in the previous scan-forward step. Thus, the probablility that any key is counted in n(i) is 1/2."
I was following this excerpt completely until the part in bold. I do not understand how they came up with 1/2. Could some help clarify this statement?
Best regards,
NewProgrammer
My question is on analyzing the time it takes to search for an element in a Skip List. As some may already know, searching for key k in a Skip List is done by a series of "drop down" and "scan forward" steps until the key with the largest value less than or equal to k is found . Below is an excerpt from my textbook (and is the source of my confusion):
"Let n(i) be the number of keys examined while scanning forward at level i. Observe that, after the key at the starting position, each additional key examined in a scan-forward at level i cannot also belong to level i + 1. If any of these keys were on the previous level, we would have encountered them in the previous scan-forward step. Thus, the probablility that any key is counted in n(i) is 1/2."
I was following this excerpt completely until the part in bold. I do not understand how they came up with 1/2. Could some help clarify this statement?
Best regards,
NewProgrammer
Topic archived. No new replies allowed.