Can $Tleft( nright) = 4Tleft({nover 2}right) + 2^{nover2}$ be solved using Akra-Bazzi method?

From

$$ Tleft(2nright)=4Tleft(nright)+2^nRightarrow Tleft(2^{log_2(2n)}right)=4Tleft(2^{log_2n}right)+2^n $$

now making

$$ mathcal{T}(cdot) = Tleft(2^{(cdot)}right), z=log_2 n $$

we have

$$ mathcal{T}(z+1)=4mathcal{T}(z)+2^{2^z} $$

solving this recurrence we obtain

$$ mathcal{T}(z) = frac 14 4^zleft(C_0+sum_{k=0}^{z-1}2^{2^k-2k}right) $$

or as $4^{log_2 n} = 2^{2log_2 n} = 2^{log_2 n^2} = n^2$

$$ T(n) = frac 14 n^2left(C_0+sum_{k=0}^{log_2 n-1}2^{2^k-2k}right) $$

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{4cdot 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)+sumlimits_{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.