Self doubt

Question

How to solve the given recurrence relation using master's theorem?

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

Comments

What is the base condition of this question?

---

not given but take appropriately..

May be T(1)=1

---

I think this question can be solved much easily using substitution method

Answer 1

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

Comments

$\Theta(n)$  is correct.

How are u getting $\theta (n \log\log n)$ ??

---

The solution to the recurrence $S(m) = S(m/2) + 2^m$

is $2^m \cdot \log m$

Substituting $\log n = m$

We get $2^{\log n} \cdot \log \log n$

Which is $O(n \cdot \log \log n)$

Correct me if I'm wrong.

---

@toxicdesire  here case 3 of masters theorem is applied..

 

$T(n)=T(n/2)+2^n\implies \Theta(2^n)$

can you share your approach?

Answer 2

T(n)= o(n)