D. J. Bernstein
Integer factorization
Circuits for integer factorization

Background: What o(1) means

The notation o(1) means ``a function that converges to 0.'' This means that there is some input size past which the function is always between -0.1 and 0.1; there is some input size past which the function is always between -0.01 and 0.01; and so on. In other words, the function is extremely close to 0 for extremely large inputs.

For example, in a traditional model of computation, a standard bubble sort will take n^(2+o(1)) seconds to sort a typical list of n small numbers. This means that

and so on.

WARNING: If you start from only the o(1) information, you cannot make predictions about any specific input size. In particular, replacing o(1) with 0 almost never produces correct results. For example:

Statements using o(1) are statements about large input sizes. They do not say anything about small input sizes, and they do not say what the cutoff is between ``small'' and ``large.''

On the bright side, statements using o(1) are typically easier, often much easier, to prove than statements that provide more information.