Skip List Expected Costs

Problem

Return the expected height and the expected search cost of a skip list with n elements and promotion probability p.

The expected number of levels is the sum over l >= 1 of 1 - (1 - p ** (l - 1)) ** n, and the search cost is (1 / p) times log base 1/p of n. Return [expected height, expected search cost], both 0.0 for invalid inputs, with cost 0.0 for n = 1.

Hint

Sum the probability that at least one node reaches each level for the expected height.

Test cases

case 1

in: [1,0.5]

expected: [1.9999999999999982,0]

case 2

in: [8,0.5]

expected: [4.42107772581558,6]

case 3

in: [100,0.25]

expected: [4.240589925677196,13.28771237954945]

case 4

in: [0,0.5]

expected: [0,0]

case 5

in: [10,0.5]

expected: [4.725559323634527,6.643856189774725]

Starter codePython

import math


def skip_list_costs(n, p):
    # Your code here
    pass

5 test cases · run your code against them in the editor