1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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