How can I obtain some good upper/lower bounds on the function
$$ f(k)= \frac{-p}{\log_2{\left( 1-2^{-k} \right)}}$$
for $0<k<p$? I have an algorithm where the runtime comes down to this expression, and I have no idea how to figure out how it will grow.
Note that for $0 < x < 1$ we have
$$x < -\ln(1-x) = \int_{1-x}^1 \frac{dt}{t} < \frac{x}{1-x},$$
and
$$-\log_2(1 - 2^{-k}) = \frac{-\ln(1 - 2^{-k})}{\ln 2}.$$
Hence,
$$\frac{1}{(\ln 2) \,2^k}= \frac{2^{-k}}{\ln 2}<-\log_2 (1 - 2^{-k}) < \frac{ 2^{-k}}{\ln 2 (1 - 2^{-k})} = \frac{1}{\ln 2(2^k - 1)}, $$
and
$$p(\ln 2)(2^k-1)<\frac{-p}{\log_2 (1 - 2^{-k})}<p(\ln 2) 2^k$$
