I find this question very tricky:
Got stuck very fast after the basics-
I have been on this for too long. Help will be much appreciated.
Asked
Active
Viewed 24 times
0
-
2You mean, you cannot define $$S(m)=T(2^{2^m})$$ then note that $$S(m)=S(m-1)+cm$$ and estimate $S(m)$? What is stopping you? – Did Apr 07 '17 at 14:51
-
Can you explain why S(m-1)=T(2^2^(m-1))? – sheldonzy Apr 07 '17 at 15:11
-
2$\sqrt{2^{2^m}} = 2^{\frac{1}{2}\cdot 2^m} = 2^{2^{m-1}}$ – Lazy Lee Apr 07 '17 at 15:15
1 Answers
1
My approach would be to let $n = 2^t$ and $F(t) = T(2^t)$. This gives us $F(t) = F\left(\frac{t}{2}\right)+\Theta(\log t)$, which we can approach with the Master Theorem with $a=1$, $b=2$, and Case 2 as in the wiki page: https://en.wikipedia.org/wiki/Master_theorem
Thus $F(t) = \Theta\left(\log^2t\right)$, and hence $T(n) = F(\log n) = \Theta\left((\log\log n)^2\right)$
Lazy Lee
- 3,631