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


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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.