Solve recurrence: T(n) = T(logn) + logn

Question

I am struggling to find a f(n) so that T(n) = $\Theta$(f(n)). I can only think of one upper bound, that is: $log^{*}(n) \cdot logn$

Any suggestion about what may f(n) be? Thanks.

Answer 1

Let’s think about the recursion tree(path) for this recurrence. There will be $\log^*(n)$ levels, and each subproblem at level $i$ has one problem of size $\log^{(i)}n$ where $\log^{(i+1)}n = \log(\log^{(i)}n)$ and $\log^{(i)}n = \log n$. As a result, for the upper bound we have $$T(n) = \log n+T(\log n) = O(\sum_{i = 0}^{\log^*(n)}\log^{(i+1)}n) = O(\log n)$$ The last equality is true because $\log n<\frac{1}{2}n$ for large enough $n$, and $\log^{(i+1)}n<\frac{1}{2^i}\log n$ and use geometric series. Moreover it's not hard to see $T(n) = \Omega(\log n)$. Therefore $T(n) = \Theta(\log n)$.