Solve the Recurrence

Question

Solve the Following Recurrence using

• Back Substitution
• Master Theorem

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

Using Master Theorem

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

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 proceed further... ?

Comments

@mcjoshi pls explain to the last.  that is so tough for me to understand . im not that good :(

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 proceed further... ?

---

You used back substitution from original recurrence equation, but i started from intermediate one.

In your case : $T(n)$ will be something like : $ n + n^\frac{1}{2} +  n^\frac{1}{4} +  n^\frac{1}{8} +  n^\frac{1}{16} + \dots + 1$, and result lies in finding summation, but i cann't find sum to this series.

We generally take some base case, say $T(1) = 1$, 

$n^\frac{1}{2^k} = 1$ and we get $k \rightarrow \infty$

---

In my modified recurrence $T(m) = T(m/2) + 2^m$

We get this series to be $2^m + 2^\frac{m}{2} + 2^\frac{m}{4} + 2^\frac{m}{8} + \dots + 1$

See my above comment where i have derived upto : $T(m) = T(\frac{m}{2^k} + 2^m + 2^\frac{m}{2} + 2^\frac{m}{4} + 2^\frac{m}{8} + \dots + 2^\frac{m}{2^k}$

now $T(1) = 1$, $\frac{m}{2^k} = 1 \Rightarrow k = log_2m$

---

@mcjoshi,

Yeah I was stuck at that summation . Thats what i was intended to ask from the begining . May be my words weren't put correctly :)

In your method also there is summation right ? You did missed constant also

$T(m) = T(\frac{m}{2^{k}}) + \sum 2^{\frac{m}{2^{i}}} + k c$

Answer 1

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

Let $n = 2^m$

$T(2^m) = T(2^\frac{m}{2}) + 2^m$

Let $T(2^m) = S(m)$, then $T(2^\frac{m}{2}) = S(\frac{m}{2})$

Recurrence reduces to : $S(m) = S(\frac{m}{2}) + 2^m$

Now both back substitution and Master's Theorem can be applied.

$S(m) = O(2^m)$ ($m = log_2n)$

$\color{red}{T(n) =O(n)}$

Comments

@mcjoshi can u consider my comment above . Im not able to understand how the last condition is satisfied

---

Iam not using Master's theorem.

---

@mcjoshi pls explain using Master theorem and back substitution .

Using Master Theorem Im stuck at the last condition of regularity check im getting it  2 <= m  . As explained in above coment . How to proceed from here . Please explain to the last.... Don't leave in the middle :(