# Bounding the recurrence $f(n)=2f(n-1)+2f(n/2)$

I met a recurrence equation for my algorithm $$f(n) = 2\cdot \left( f(n-1) + f(\frac{n}{2}) \right)$$ with $f(1)=1$, $f(2)=4$, $f(3)=10$.

I guess it is $\Theta((2+\epsilon)^n)$, where $\epsilon$ ban be arbitrarily close to 0. I want to have an asymptotic formula of $f(n)$. I do not know how to prove or disprove my guess.

• A good start would be to notice that it's easy to show that $f(n) \in \Omega(2^n)$ since $f′= 2\cdot f\prime(n−1)$ and $f\prime (n)\in \Omega(2^n)$ and $f\prime (n) \leq f(n)$** – Francesco Gramano Apr 9 '14 at 19:46
• @FrancescoGramano Yes. my guess is in $\Omega(2^n)$. But I do not how to prove it rigorously. – Peng Zhang Apr 9 '14 at 19:56
• How do you get to this guess? What have you tried towards a proof? I don't see much more than a problem dump. – Raphael Apr 9 '14 at 21:46

For concreteness, let's assume that your recurrence is really $$f(n) = 2f(n-1) + f(\lfloor n/2 \rfloor) + f(\lceil n/2 \rceil).$$ Define $g(n) = f(n)/2^n$. Then $$g(n) = g(n-1) + 2^{\lfloor n/2 \rfloor + 1 - n} g(\lfloor n/2 \rfloor) + 2^{\lceil n/2 \rceil + 1 - n} g(\lceil n/2 \rceil).$$ In particular, $$g(n) \leq (1 + 2^{\lfloor n/2 \rfloor + 1 - n} + 2^{\lceil n/2 \rceil + 1 - n}) g(n-1).$$ Taking logarithms, $$\log g(n) \leq \log g(n-1) + O(2^{\lfloor n/2 \rfloor + 1 - n} + 2^{\lceil n/2 \rceil + 1 - n}).$$ We conclude that $$\log g(n) \leq O(1) + O(1) \sum_{m=c}^n [2^{\lfloor m/2 \rfloor + 1 - m} + 2^{\lceil m/2 \rceil + 1 - m}] = O(1),$$ where $c$ is some arbitrary starting point. Therefore $\log g(n)$, and so $g(n)$, is bounded. Since clearly $g(n)$ is monotone increasing, we deduce that $g(n)$ tends to some constant $C$. We conclude that $$f(n) \sim C 2^n.$$
• Thank you a lot. It is amazing go see that $g(n)$ is bounded by some constant. – Peng Zhang Apr 9 '14 at 20:26