What does o(1) stand for?

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?

---

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) < kg(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) < kg(x) holds for all x > a.

---

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.

链接地址: http://www.djcxy.com/p/39890.html

上一篇: 对数函数的渐近复杂性

下一篇: o（1）代表什么？