2
$\begingroup$

Let $$f(k) := \frac{2k-1}{k}\bigl(1-\sum\limits_{i\lt k}\frac{i\ f(i)}{k+i-1}\bigr)$$ for $k\in\mathbb{N}^{+}$.

So $f(1) = 1$, $f(2) = 3/4$, $f(3) = 35/72$, etc.

(This function arises when calculating an upper bound for the worst-case behaviour of the first-fit algorithm for dynamic storage allocation.)

Numerically it appears that $f(n)$ is approximately $1/(n\ ln(2))$. Can anyone give me any hints as to how one might try to prove that, or even a bound like $f(n) < 2/n$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Rewriting the recursion yields $$1 = \sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1}.$$ By assuming $f(k)=\frac{1}{k \ln 2} (1+o(1))$ --- where the little o-Notation $o(1)$ simply means that it is smaller than every constant for large $k$ --- and inserting this, we get $$\sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1} = \frac{1}{\ln 2} \sum\limits_{1\leq i \leq k} \frac{1+o(1)}{k+i-1} = \frac{1+o(1)}{\ln 2} \left(\ln (2k-1)-\ln(k)\right) = \frac{1+o(1)}{\ln 2} \ln\left(2-\frac1k\right) \to 1 $$ for $k\to\infty$. I used $\sum_{1\leq i \leq k} \frac1i = \ln k + \gamma + o(1)$. Therefore the assumtion holds asymptotically, since it fulfils the recursion.

The bound $f(k)<2/k$ follows from that --- at least, there is an $K$, such that for all $k\geq K$ the inequality $f(k)<2/k$ holds.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.