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