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


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)$.)
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$.)
Suppose that $T(1) = C$. Can you come up with a formula for $T(n)$? Can you deduce a tight asymptotic bound?