1

I'm trying to implement the Quadratic Sieve, and i noticed i need to choose a smoothness bound B to use this algorithm. I found in the web that B also stands for exp((1/2 + o(1))(log n log log n)^(1/2)) but now my problem is o(1). Could you tell me what does o(1) stand for?

Gabe
  • 84,912
  • 12
  • 139
  • 238
Michael
  • 1,018
  • 4
  • 14
  • 30
  • http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly?rq=1 – Sam Jun 02 '14 at 04:54
  • dont be mean :c didnt notice – Michael Jun 02 '14 at 05:00
  • 1
    I'd recommend posting links to explain what you found. It's quite possible that you misunderstood something or that something you wrote only makes sense in context. – Gabe Jun 02 '14 at 05:02
  • I found it here : http://www.math.leidenuniv.nl/~reinier/ant/sieving.pdf .. The choice of the smoothness bound section – Michael Jun 02 '14 at 05:07
  • 2
    @AndersLindén Actually it's `o(1)`, not `O(1)` (they're different), so I don't believe it's a duplicate. Also, the linked post just gives examples (which is too broad, by the way) - not exactly a particularly rigorous explanation of any of them. – Bernhard Barker Jun 03 '14 at 15:52
  • Ok, I had removed my comment about the posting being a possible duplicate – Anders Lindén Jun 03 '14 at 16:08

2 Answers2

6

Let's start with your answer:

The definition of f(n) being o(1) is that limn→∞f(n)=0. That means that for all ϵ>0 there exists Nϵ, depending on ϵ, such that for all n≥Nϵ we have |f(n)|≤ϵ.

Or in plain English:

The notation o(1) means "a function that converges to 0."

This is a fantastic resource: http://bigocheatsheet.com

Look at the Notation for asymptotic growth section

The answer can also be found in this duplicate post: Difference between Big-O and Little-O Notation

f ∈ O(g) says, essentially

For at least one choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a.

Note that O(g) is the set of all functions for which this condition holds.

f ∈ o(g) says, essentially

For every choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a.

Community
  • 1
  • 1
bstar55
  • 3,542
  • 3
  • 20
  • 24
  • So I guess if we have `o(1)`, that means `f` tends to `0` (that's the only constraint for a (non-negative) function I can find that fits the definition). – Bernhard Barker Jun 03 '14 at 16:34
  • Correct. The notation o(1) means "a function that converges to 0." - http://cr.yp.to/nfscircuit/o1.html – bstar55 Jun 03 '14 at 16:44
-1

O(1) means it takes constant time, unaffected by input size. o(1) (slightly different!) means the function it represents converges to 0. I wouldn't worry too much about the smoothness bound, write the rest of the much more complicated algorithm first, using very simple smoothness formula. (first 100,000 primes, or first n primes where n = c *log(number)) Once the rest of the algorithm is working (and perhaps optimized?) then choosing a smoothness bound carefully will actually have a significant effect. That long complicated formula you gave in the question is the approximate (asymptotic) running time for the quadratic sieve algorithm itself, I'm pretty sure it is unrelated to choosing the smoothness bound.

Straw1239
  • 589
  • 2
  • 8