Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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