0
$\begingroup$

I have homework from recursion tree and despite my search for hours I could not find the answer to this problem.

I appreciate if you can help.

Draw a recursion tree and give a tight asymptotic bound on the solution of the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$. You need not prove your answer.

$\endgroup$
  • $\begingroup$ The way to find and answer to a problem is to try to solve it yourself! $\endgroup$ – Yuval Filmus Nov 4 '14 at 5:18
  • $\begingroup$ Do you know what a recursion tree is? $\endgroup$ – Yuval Filmus Nov 4 '14 at 5:19
  • $\begingroup$ In order to give you a helpful answer we need to know what you have tried and where, specifically, you got stuck. $\endgroup$ – Raphael Nov 4 '14 at 6:42
  • $\begingroup$ I don't see how this is a duplicate question, the word "tree" doesn't appear once in the linked question therefore whether or not the linked question answers general questions about asymptotic behavior it does not give examples of using a recursion tree (which is a pretty standard technique). $\endgroup$ – Jared Nov 4 '14 at 6:43
0
$\begingroup$

I don't know what a recursion tree is, but I know how to expand a formula: $$ \begin{align*} T(n) &= 2^{n/2} T(n/2) + 2^n \\ &= 2^{n/2} (2^{n/4}T(n/4) + 2^{n/2}) + 2^n \\ &= 2^{(3/4)n} T(n/4) + 2^n + 2^n \\ &= 2^{(3/4)n} (2^{n/8} T(n/8) + 2^{n/4}) + 2^n + 2^n \\ &= 2^{(7/8)n} T(n/8) + 2^n + 2^n + 2^n \\ &= \cdots \end{align*} $$ You take it from here, along the following lines:

  1. Assume that $n$ is a power of $2$. How many times do we need to apply the recurrence identity until we get to $T(1)$? (Above I applied it three times and got down to $T(n/8)$.)

  2. When we do get to $T(1)$, what are we left with? (When we get down to $T(n/8)$, we are left with $2^{(7/8)n} T(n/8) + 3\cdot 2^n$.)

  3. Suppose that $T(1) = C$. Can you come up with a formula for $T(n)$? Can you deduce a tight asymptotic bound?

$\endgroup$

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