Question

Computer Science 1. Suppose the probability of getting a head when tossing a coin during the construction of a skip list is p for some 0 < p < 1. a. Show that the expected search path length in a skip list of size n is at most 1/p * log 1/p (n) + O(1) . (The base of the logarithm is 1/p.) b. Also for what value of p is this expression minimized?​

Answer 1

Answer:

The skip list is a probabilisitc data structure that is built upon the general idea of a linked list. The skip list uses probability to build subsequent layers of linked lists upon an original linked list. Each additional layer of links contains fewer elements, but no new elements.

Explanation:

I hope it's help you please mark me as a brain list