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?

1 Answers 1

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.