#algorithm#analysis

Question

How to solve T(n) = T(n^(1/2)) + n by using master's theorem? if not by masters theorem give another approach.

Comments

you can not solve it by master theorem...

but you can solve it by using back substitution algorithm

Answer 1

At first we convert into aT(n/2)+f(n) fome . And after we can apply master theorem.

Comments

can you provide some source where master theorem is applicable in this form?

---

@abhishekmehta4u  Thanks :)

Answer 2

$\text{I'm trying to solve the recurrence relation:}$

$$T(n) = T(\sqrt n) + n$$

$\text{My first step was to let $n=2^{m}$}$

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

$\text{if S(m) = $T(2^m)$ then,}$

$$S(m) = S(m/2) + 2^m$$

 $\text{This is an easier recurrence to solve.}$

$\text{If I try and use the Master Theorem, I calculate $n^{\log_b a}$}$

$\text{where a=1 and b=2 to be $n^{\log_2 1}$ which gives $n^0=1$.}$

$\text{It seems like this might be case 2 of the Master Theorem where }$

$\text{ $n^{\log_b a}$<f(n),where f(n)=$2^m$}$

$\text{According to master's condition T(n)=$\theta(f(n)(logn)^k)$where $k>=0$)}$

$\text{T(n)=$\theta(2^m)$}$

$\text{so,Ans is $T(n)=\theta(n)$}$

Answer 3

Tree Method you can use

                n elements----------------------------cost is n

                n^1/2 elements---------------cost is n^1/2

                n^(1/2^2) elements-------------cost is n^(1/2^2)

        ............................

              Similarly this will go up to log logn levels.....how i got it....  see this  n^(1/2^k)=2....

             solving this you will get k=loglogn where k in no. of levels

so you got series =n+n^1/2+n^(1/2^2)+................................+n^(1/2^loglogn) as its decreasing gp series sum would be O(n)

so your answer will be=O(n)