Found the random search limit #57
Description
The slowdown for randomized binary search versus the normal version is 2*log(2), about 1.386. Doesn't require much calculus in the end: the randomized time simplifies to twice the harmonic series, which has the well-known sum log(n) + O(1). Dividing by log2(n) causes the O(1) part to go to 0 (slowly), and log(n) / log2(n) is the constant log(2).
Flattening the recurrence, starting from your linear-time version:
# From random-binsearch.py
g[k] = (s[k - 1] * 2 / k / (k - 1) + 1) * k
= 2 * s[k - 1] / (k - 1) + k
s[k] = s[k - 1] + g[k]
# Substitute g
s[k] = s[k - 1] * (1 + 2 / (k - 1)) + k
= s[k - 1] * (k + 1) / (k - 1) + k
(s[k] / k) = s[k - 1] * (1 + 1 / k) / (k - 1) + 1
# Define r
r[k] = s[k] / k
r[k] = r[k - 1] * (1 + 1 / k) + 1
# Rewrite original g recurrence in f and r
f[k] * k = 2 * r[k - 1] + k
r[k - 1] = (f[k] - 1) * k / 2
# Substitute into r recurrence
(f[k + 1] - 1) * (k + 1) / 2 = (f[k] - 1) * k / 2 * (1 + 1 / k) + 1
= (f[k] - 1) * (k + 1) / 2 + 1
(f[k + 1] - 1) = (f[k] - 1) + 2 / (k + 1)
f[k + 1] = f[k] + 2 / (k + 1)
f[k] = f[k - 1] + 2 / k