How can I solve the following recurrence relation? $$ f(n) = f(n-1) + f(n - \log n)$$
$\begingroup$
$\endgroup$
3
-
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 ChekuriCommented Jan 29, 2016 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$– gregCommented Jan 29, 2016 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řábekCommented Jan 29, 2016 at 12:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
@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)}$.