1
$\begingroup$

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

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

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.