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

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

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

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

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

T(n)= o(n)

1
299 views