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

$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.

• $T(n)=O(\log n)$ verifies $T(n)=T(\log n)+O(\log n)$ [and can't be improved] – user8268 Oct 19 '13 at 16:45

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