What is the base condition of this question?

Dark Mode

449 views

2 votes

Best answer

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

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

0

@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?

0