edited by
2,161 views
0 votes
0 votes

Give asymptotic upper and lower bound for $T(n)$ given below. Assume $T(n)$ is constant for $n \leq 2$. $T(n) = 4T( \sqrt{n} ) + \lg^2n$

  1. $T(n) = \theta (\lg ( \lg ^2 n) \lg n )$
  2. $T(n) = \theta ( \lg ^2 n \lg n )$
  3. $T(n) = \theta (\lg ^2 n \lg \lg n )$
  4. $T(n) = \theta (\lg ( \lg n) \lg n )$
edited by

2 Answers

9 votes
9 votes

$\mathbf{\underline{Answer:}\Rightarrow}\;\text{Option}\;3)\;\bbox[lightblue,5px,border: 2px solid blue]{\mathbf{T(n) = \Theta \left (\log^2n.\log\log n\right )}}$

$\mathbf{\underline{Explanation:}\Rightarrow}$

$\mathrm{T(n) = 4T(\sqrt n) + \log ^2 n}$

Let $\mathrm{n=2^m \Rightarrow m = \log_2n}$

$\mathrm{\Rightarrow T(2^m) = 4 T(2^{\frac{m}{2}}) + \log^2 (2^m)}$

$\mathrm{\Rightarrow T(2^m) = 4 T(2^{\frac{m}{2}}) + \log (2^m)\times \log(2^m)}$

Now,

$\mathrm{S(m) =T(2^m) }$

$\mathrm{\Rightarrow S(m) = 4S\left (\dfrac{m}{2}\right) + m\times m}$

$\mathrm{\Rightarrow S(m) = 4S\left (\dfrac{m}{2}\right) + m^2}$


Now, On applying the $\underline{\textbf{Master's Theorem}}$, we get:

$\mathrm{Here, \;a = 4, b = 2, k = 2, p = 0}$

$\therefore \mathrm{a = b^k \Rightarrow 4 = 2^2,\;and\;k = 2, p > 0}$

$\therefore\mathbf{Case\;2\;(i)}$  

$\mathrm{T(n) = \Theta(n^{\log_ba}\log^{p+1}n)\;\;,\text{where}\;a = b^k, p>-1}$

$$\therefore\mathrm{T(n) = \Theta(m^{\log_24}\log^{0+1}m)\\=\Theta(m^{\log_22^2}\log^{0+1}m)\\=\Theta(m^{2\log_22}\log^{0+1}m)}$$

$\Rightarrow \mathrm{T(n)= \Theta (m^2\times \log^1m)} \tag{1}$

Now, $\because\mathrm{ m = \log_2n}$

Substituting this value of $\mathbf{m}$ in $(1)$, we get:

$\bbox[lightblue,5px,border: 2px solid blue]{\mathbf{T(n) = \Theta \left (\log^2n.\log\log n\right )}}$

$\therefore \mathrm{option(3)}$ is the right answer.


Refer: Problem $1-2$ Recurrences:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf


Master's Theorem Reference:

 

 

edited by
2 votes
2 votes

Using Back Substitution :

$\mathrm{T(n) =4T(n^{1/2}) + (\lg n)^2}$

$\mathrm{= 4[4T(n^{1/4}) + (\frac{1}{2})^2 (\lg n)^2] + (\lg n)^2}$

$\mathrm{\Rightarrow T(n)= 4^2 T(n^{1/4}) + 4 (\frac{1}{2})^2 (\lg n)^2 + (\lg n)^2}$

$\mathrm{=4^2[4T(n^{1/8}) + (\frac{1}{4})^2 (\lg n)^2] + 4 (\frac{1}{2})^2 (\lg n)^2 + (\lg n)^2}$

$\mathrm{= 4^3T(n^{1/8}) + 4^2 (\frac{1}{4})^2 (\lg n)^2 + 4 (\frac{1}{2})^2 (\lg n)^2 + (\lg n)^2}$

$\mathrm{= 4^3[4T(n^{1/16}) + (\frac{1}{8})^2 (\lg n)^2] + 4^2 (\frac{1}{4})^2 (\lg n)^2 + 4 (\frac{1}{2})^2 (\lg n)^2 + (\lg n)^2}$

$\mathrm{= 4^4T(n^{1/16}) + 4^3(\frac{1}{8})^2 (\lg n)^2 + 4^2 (\frac{1}{4})^2 (\lg n)^2 + 4 (\frac{1}{2})^2 (\lg n)^2 + (\lg n)^2}$

$\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots$

$\dots\dots\dots\dots\dots\dots\dots\dots\dots$

$\mathrm{\Rightarrow T(n)= 4^k T(n^{\frac{1}{2^k}}) + 4^{k-1}(\frac{1}{2^{k-1}})^2(\lg n)^2 + 4^{k-2}(\frac{1}{2^{k-2}})^2(\lg n)^2 + \dots\dots+ 4^3(\frac{1}{2^3})^2 (\lg n)^2 + 4^2 (\frac{1}{2^2})^2 (\lg n)^2 + 4^1 (\frac{1}{2^1})^2 (\lg n)^2 + (\lg n)^2}$

Now, Assuming, $\mathrm{T(2) = 1}$. So, $\mathrm{n^{\frac{1}{2^k}} = 2 \Rightarrow n = 2^{2^k} \Rightarrow \lg n = 2^k \Rightarrow \lg\lg n = k}$

So, $\mathrm{4^k = 4^{\lg\lg n} = (2^{(2)})^{\lg \lg n} = 2^{2\lg\lg n} = 2^{\lg(\lg n)^2} = (\lg n)^2}$

So, now recurrence becomes :

$\mathrm{T(n) = (\lg n)^2 \times 1 + (\lg n)^2[ 1+ 1 + 1 +\dots\dots k \; times ]}$

$\mathrm{T(n) = (\lg n)^2 + (\lg n)^2 \times k}$

$\mathrm{T(n) = (\lg n)^2 + (\lg n)^2 \lg\lg n}$

$\mathrm{T(n) = \Theta( (\lg n)^2 \lg \lg n)}$

edited by

Related questions

1 votes
1 votes
2 answers
1
4 votes
4 votes
6 answers
3
soujanyareddy13 asked May 12, 2021
1,859 views
The Boolean expression $AB+A \overline{B}+\overline{A}C+AC$ is unaffected by the value of the Boolean variable _________.$A$$B$$C$$A, B$ and $C$