Ace practice book closed

Question

how to apply master's method for this recurrence relation

$T\left ( n \right )= {}\sqrt{n}T\left ( {\sqrt{n}} \right )+n$

Answer 1

Master Theorem can not be applied. We have to solve it by substitution method.

Answer 2

T(n) = $n^{1/2}$T($n^{1/2}$) + n

put n=$2^{m}$

T($2^{m}$) = $2^{m/2}$T($2^{m/2}$) + $2^{m}$

divide by $2^{m}$

$\frac{T(2^{m})}{2^{m}} = \frac{T(2^{m/2})}{2^{m/2}} + \frac{2^{m}}{2^{m}}$

put $\frac{T(2^{m})}{2^{m}}$ = S(m)

then , S(m) = S(m/2) + 1

By master theorem S(m) = $\Theta(logm)$

T($2^{m}$) = $2^{m}$.S(m) = $2^{m}$.$\Theta(logm)$

now m = logm

T(n)= $\Theta(nloglogn)$

Answer 3

here we can not apply Master theorem

if  any recurrence relation is the form of

T(n) = a T(n/b) + f(n)

where  a and b should be +ve constant and a ≥ 1,b >1

and f(n) be +ve function