random-binsearch.py

from math import log2

n = 10**6

# O(n^2) algorithm:

"""
f = [0] * n

for k in range(2, n):
    for l in range(1, k):
        r = k - l
        f[k] += (f[l] * l + f[r] * r) / k
    f[k] /= (k - 1)
    f[k] += 1

f[n - 1] / log2(n)
"""

# O(n) algorithm:

g = [0] * n
s = [0] * n

for k in range(2, n):
    g[k] = (s[k - 1] * 2 / k / (k - 1) + 1) * k
    s[k] = s[k - 1] + g[k]

g[n - 1] / (n - 1) / log2(n)

# what is the limit of g[n]?