Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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.