Solving Recurrences - find an asymptotically right bound

Question

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.

Answer 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)$