Example $2\mathrm{.}11.$ Solve the following recurrence relation for $n=2^k$ for any

positive integer $k.$ If $n$ is not a power of $2,T(n)$ is bounded by the $T$ values

of two consecutive powers of $2$ and hence will belong to the same efficiency

class as with the powers of $2.$

$T(n)=T(\frac{n}{2})+n$ for $n>1$ and $T(1)=1.$

Solution: $T(n)=T(2^k)=T(2^{k-1})+2^k=[T(2^{k-2})+2^{k-1}]+2^k=$cdots$=$

$1+2+2^2+$cdots$+2^k=2^{k+1}-1=2*2^k-1=2n-1.$ using this example solve T$($n$)=$ T$($n$/3)+1$ for n $>1$ and T$(1)=1.$ Assume n is a power of $3.$