Quick question on mathematical notation (translating to C)

Quote:

---

Originally Posted by gardhr

I'm basing it on the heuristic that most papers written about number theory seem to use that convention.

Specifically, it's a lower bound given for the Miller-Rabin primality test, described here.

---

The expression is in the context of computational complexity, and indeed it is used in "big-O" notation throughout the paper. Basically, the base does not matter since they are considering things "asymptotically".

Quote:

---

Originally Posted by laserlight

The expression is in the context of computational complexity, and indeed it is used in "big-O" notation throughout the paper. Basically, the base does not matter since they are considering things "asymptotically".

---

The equation in question relates to the actual lower bound of trial number bases, not the complexity of the algorithm. Or am I reading it wrongly?

"For an integer n , let G(n) denote the smallest x such that the
primes < x generate the multiplicative group modulo n . We offer heuristic
arguments and numerical data supporting the idea that
G(n) < (log 2)^-1 log n log log n"