How to Solve the following Recurrence Equation?

Question

I wanted to Solve the following Recurrence Equation using Master Theorem and Back substitution but Im stuck at certain point . can u pls help me how to proceed further

$T(n)=T(\sqrt{n})+n+c$

Using Master Theorem,

put n = $2^{m}$

$ T(n)=T(2^{m})= S(m)$ ie $T(\sqrt{n}) = S(\frac{m}{2})$

Hence the Recurrence Relation will be $S(m)=S(\frac{m}{2})+ 2^{m}$

Here a =1 , b=2 $f(m)=2^{m}$

case 1 : $2^{m} \notin O(m^{\log_b a - \epsilon })$

case 2 : $2^{m} \notin \Theta (m^{\log_b a } \log^{k} n)$

case 3 : $2^{m} \in \Omega (m^{\log_b a +\epsilon } )$

put $\epsilon = 1$ We get

$2^{m} \in \Omega (m^{\log_2 1 +1 } ) \Rightarrow \Omega (m^{0+1})\Rightarrow \Omega (m)$ Which is True

Now checking Regularity

$af(\frac{m}{b})\leq \delta f(m) \Rightarrow f(\frac{m}{2})\leq \delta f(m)$

ie .$2^{\frac{m}{2}} \leq \delta \ 2^{m}$ taking log on both sides $\frac{m}{2}\leq \log_2 \delta +m$

taking $\delta =\frac{1}{2}$

$\frac{m}{2}\leq -1 +m \Rightarrow 1 \leq \frac{m}{2} $

How to check this last condition is satisfied or not ? How to proceed from here... ?

Using back Substitution $T(n)=T(\sqrt{n})+n+c$

$T(n)= T(n^{\frac{1}{2}})+n+b \\ = T(n^{\frac{1}{4}})+n^{\frac{1}{2}}+n+2b \\ =T(n^{\frac{1}{8}})+n^{\frac{1}{4}}+n^{\frac{1}{2}}+n+3b \\ ... \\ .. \\ = T(n^{\frac{1}{2^{k}}})+\sum_{i=1}^{k} n^{\frac{1}{2^{i}}} + kb$

How to Evaluate the summation ? How to proceed further... ?

please explain both the method.

Answer 1

Regarding the master method, I don't quite understand why you got stuck. You had to show that the function $f(n) = 2^n$ satisfies $f(n/2) \leq (1-\epsilon) f(n)$ for some $\epsilon > 0$ and large enough $n$. You showed this using some complicated calculation. So the condition is satisfied, and the method applies, giving the answer $T(2^m) = \Theta(f(m)) = \Theta(2^m)$. A more elementary way to check the condition is to notice that when $n \geq 2$, $$ 2^{n/2} \leq 2^{n-1} = \frac{1}{2} \cdot 2^n. $$

Regarding substitution, clearly $f(n) \geq n + c$. In the other direction, when $n \geq M$ we have $\sqrt{n} \leq n/\sqrt{n} \leq n/\sqrt{M}$, $\sqrt[4]{n} \leq \sqrt{n}/\sqrt{M} \leq n/M$, and so on. Therefore when $n^{1/2^{k+1}} \geq M$, $$ \begin{align*} f(n) &= n + c + \sqrt{n} + c + \cdots + n^{1/2^k} + c + f(n^{1/2^{k+1}}) \\ &\leq n + \frac{n}{\sqrt{M}} + \cdots + \frac{n}{\sqrt{M}^k} + (k+1) c + f(n^{1/2^{k+1}}) \\ &\leq n \sum_{t=0}^\infty \frac{1}{\sqrt{M}^t} + (k+1)c + f(n^{1/2^{k+1}}) \\ &= \frac{1}{1-1/\sqrt{M}} n + (k+1)c + f(n^{1/2^{k+1}}). \end{align*} $$ Choosing $k$ so that $n^{1/2^{k+1}} \approx M$, we deduce that $$ f(n) \leq \frac{1}{1-1/\sqrt{M}} n + O(c\log\log n), $$ where the hidden constant depends on $M$. Choosing an arbitrary $M$, we get $f(n) = O(n)$. This implies that $$ f(n) = n + c + f(\sqrt{n}) = n + O(\sqrt{n}). $$ Combining this with the lower bound, we have $$ n + c \leq f(n) \leq n + O(\sqrt{n}). $$ This is a much better estimate than the one we got using the master theorem.