Finding the upper bound for this recursion: $T(n) = T(\log n) + O(\log n)$

Question

$T(n) = T(\log n) + O(\log n)$

So I came up with this: $T(n) \le T(\log(\log n)) + C\log n + C\log(\log n)$

And then: $T(n) \le C(\log n + \log(\log n) + \log(\log(\log n)) + ... )$

And so my problem is I dont know how many organs are summed in the brackets, Any suggestions? Thank you in advance.

Answer 1

There are $O(\log^* x)$ terms in the summation (assuming you're doing something reasonable). But you don't need to know that: $\log n$ dominates them all individually, so you just need to know there aren't too many. e.g. showing that there are

$$ o\left( \frac{\log n}{\log \log n} \right) $$

because all of the remaining terms are $O(\log \log n)$, and

$$ o\left( \frac{\log n}{\log \log n} \right) \cdot O(\log \log n) = o(\log n)$$

(a much lower bound that the one mentioned above is easy to prove)