Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the paper Wherefor Art Thou R3579X? they state at the end of page 5, while proving theorem 2.2, that "Once $j$ is $\Theta(\log \log n)$, each term in the sum is $O(1)$".

My question is now what does "Once $j$ is $\Theta(\log \log n)$" mean? Does this have a proper definition or is it just more abuse of asymptotic notation?

share|cite|improve this question

My take on this is that there are real positive constants $a$ and $b$ such that $$a \log \log n < j < b\log \log n $$

Evidently (since I have not read the original reference), this will allow you to deduce that the terms referred to are $O(1)$.

(Added a bit later)

If you want to keep this completely in terms of $O(...)$ notation, both $j = O(\log \log n)$ and $\log \log n = O(j)$ hold.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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