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 TrueNow 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.
How to Solve the following Recurrence Equation?
algorithms;time complexity;recurrence relation