2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)$** $\endgroup$ – Francesco Gramano Apr 9 '14 at 19:46
  • $\begingroup$ @FrancescoGramano Yes. my guess is in $\Omega(2^n)$. But I do not how to prove it rigorously. $\endgroup$ – Peng Zhang Apr 9 '14 at 19:56
  • 2
    $\begingroup$ How do you get to this guess? What have you tried towards a proof? I don't see much more than a problem dump. $\endgroup$ – Raphael Apr 9 '14 at 21:46
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ If you really want, you can obtain a complete asymptotic series this way. $\endgroup$ – Yuval Filmus Apr 9 '14 at 20:12
  • $\begingroup$ Thank you a lot. It is amazing go see that $g(n)$ is bounded by some constant. $\endgroup$ – Peng Zhang Apr 9 '14 at 20:26

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.