Can $T\left( n\right) = 4T\left({n\over 2}\right) + 2^{n\over2}$ be solved using Akra-Bazzi method?

100 Views Asked by At

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

2

There are 2 best solutions below

0
On

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.

0
On

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