12
$\begingroup$

How can I solve the following recurrence relation? $$ f(n) = f(n-1) + f(n - \log n)$$

$\endgroup$
  • 5
    $\begingroup$ What do you get if you try $f(n) = 2f(n - \log n)$? It appears that you will get a lower bound of $2^{\Omega(n/\log n)}$. $\endgroup$ – Chandra Chekuri Jan 29 '16 at 3:00
  • 2
    $\begingroup$ @ChandraChekuri Oh, that's great! And there's an upper bound of $2^{O(n \log \log n / \log n)}$: we use the recurrence $\log n$ times, and get that $f(n) \le (1 + \log n) f(n - \log n)$. Then we apply this $n / \log n$ times and get $f(n) \le (1 + \log n)^{n / \log n} = 2^{O(n \log \log n / \log n)}$. So the gap between the upper bound and lower bound is only $\log \log n$ in the exponent. This is actually enough for my purposes, but I'll leave the question open in case someone wants to and is able to close the gap. Thank you very much, Chandra! $\endgroup$ – mobius dumpling Jan 29 '16 at 3:14
  • 4
    $\begingroup$ Well, the same trick gives $f(n)\ge(\log n)f(n-2\log n)$, so $f(n)=2^{\Theta(n\log\log n/\log n)}$. $\endgroup$ – Emil Jeřábek Jan 29 '16 at 12:04
14
$\begingroup$

@Chandra, @Emil, and myself solved the question in the comments. The solution is $$f(n) = 2^{\Theta(n \log \log n / \log n)} \ .$$

To see the lower bound, apply the recurrence definition $\log n$ times, to get $$f(n) = 2f(n - \log n) + f(n - \log n - 1) + \ldots + f(n - 2 \log n) \ge \log n \cdot f(n - \log n) \ .$$ Use this inequality $n / \log n$ times, and we get that the solution is $2^{\Omega(n \log \log n / \log n)}$.

To get the upper bound, use the recurrence $\log n$ times and get that $$f(n) \le (\log n + 1) \cdot f(n - \log n) \ . $$ Use this inequality $n / \log n$ times, and we get that the solution is $2^{O(n \log \log n / \log n)}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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