Can $T\left( n\right) = 4T\left({n\over 2}\right) + 2^{n\over2}$ be solved using Akra-Bazzi method? $$T\left( n\right) = 4T\left({n\over 2}\right) + 2^{n\over2}$$
Using Akra-Bazzi method
$a = 4, b = {1\over2}, g(n) = 2^{n\over2}, h(n) = 0$
$$g'(n) = {d\over dx}(2^{n\over2})=2^{{n\over2}-1}\ln 2$$
Since $\left|g'(n)\right|$ is not polynomially bound we cannot proceed further with Akra-Bazzi method.
Using Master theorem
$a = 4, b = 2, g(n) = 2^{n\over 2}$
$g(n) = \Omega(n^{\log_2 4+\epsilon})$ where $\epsilon=1$, also
$$ag\left( {n\over b}\right) \le cg(n)$$
$$4g\left( {n\over 2}\right) \le cg(n)$$
$$2^{{n\over 4}+2} \le c2^{n\over 2} \tag*{for $c={1\over 2}$ and $n\ge 12$ }$$
Therefore it follows from master theorem that $T(n) = \Theta\left( g(n)\right) = \Theta\left( 2^{n\over 2}\right)$.
How come the above problem can be solved using Master theorem which is just a corollary of Akra-Bazzi method but not using Akra-Bazzi method itself.
 A: Starting with $$T(2n)=4T(n)+2^n$$

In this case, a possibility is to try to get $U(p)=\sum f(k)$ by introducing a telescoping relation for $U$ : $U(p+1)=U(p)+f(p)$.
To do that we first set $n=2^p$ so as to deal with the $T(2n)$ .vs. $T(n)$ relation.
And to make the proportionality coefficient $4$ disappear we will introduce the coefficient $4^p$.
Let set $$T(n)=T(2^p)=4^p\,U(p)$$
Substitution in the equation gives:
$\require{cancel}T(2n)=T(2^{p+1})=\cancel{4^{p+1}}U(p+1)=4T(n)+2^n=\cancel{4\cdot 4^p}\,U(p)+2^{2^p}$
After regrouping $U$ terms on one side and $f$ terms on the other side:
$U(p+1)-U(p)=2^{2^p}/4^{p+1}=\underbrace{2^{(2^p-2p-2)}}_{f(p)}$
And you can sum it to $$U(p)=U(0)+\sum\limits_{k=0}^{p-1} 2^{2^k-2k-2}$$
Asymptotically this sum is equivalent to its last term $2^{(2^{p-1}-2(p-1)-2)}$ because $2^{2^k}$ is growing very fast (use Cesaro for instance).
In the end $$T(n)\sim 4^p\,2^{(2^{p-1}-2p)}=2^{(2^p/2-2p+2p)}=2^{n/2}$$
Therefore because $2^{n/2}$ grows very fast we have $4T(n/2)\ll T(n)$ and $T(n)$ is just asymptotically equivalent to this growing term.
A: From
$$
T\left(2n\right)=4T\left(n\right)+2^n\Rightarrow T\left(2^{\log_2(2n)}\right)=4T\left(2^{\log_2n}\right)+2^n
$$
now making
$$
\mathcal{T}(\cdot) = T\left(2^{(\cdot)}\right),\ \ \ z=\log_2 n
$$
we have
$$
\mathcal{T}(z+1)=4\mathcal{T}(z)+2^{2^z}
$$
solving this recurrence we obtain
$$
\mathcal{T}(z) = \frac 14 4^z\left(C_0+\sum_{k=0}^{z-1}2^{2^k-2k}\right)
$$
or as $4^{\log_2 n} = 2^{2\log_2 n} = 2^{\log_2 n^2} = n^2$
$$
T(n) = \frac 14 n^2\left(C_0+\sum_{k=0}^{\log_2 n-1}2^{2^k-2k}\right)
$$
