<p>If you want to see if a number is prime naively you try all of its potential factors. A little more cleverness shows that <code>sqrt(n)</code> factors are enough.</p>
<p>One of the best methods is the Quadratic Sieve, which takes <code>exp( sqrt( ln n lnln n ))</code> which is <code>o(sqrt(n))</code>.</p>
<p><a href="https://mathworld.wolfram.com/QuadraticSieve.html" rel="nofollow noreferrer">https://mathworld.wolfram.com/QuadraticSieve.html</a></p>
<p>I know that you can't teach the quadratic sieve to your students, but they will understand the complexity of the naive algorithm, and that it start taking lots of time for large numbers: just code it out. Now &quot;little-oh&quot; means that for n large enough this is more than 5 times as fast. And for even larger n it's 50 times as fast. And for much much larger n it's 500 times as fast. Et cetera.</p>
<p>So big-oh tells you how fast an algorithm is, little-oh tells you that it's essentially faster than another algorithm.</p>

CC BY-SA 4.0
2023-02-07T00:46:51.160Z
2023-02-11T13:47:06.590Z
2023-02-11T13:47:06.590Z
Victor Eijkhout
<p>Who is this &quot;we&quot; of which you speak? Note that Big-O and related concepts precedes the computational and algorithmic use. It is a concept of mathematics that is useful in analyzing the asymptotic behavior of functions: no computers need apply.</p>
<p>It has been applied to algorithmic analysis since the behavior of algorithms, usually, on large sets of data, can be described in mathematical (functional) terms.</p>
<p>See the <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow noreferrer">wikipedia article</a> for a discussion and comparison of the various concepts.</p>
<p>But to answer part of your question explicitly, if we know that a process with behavior g is efficiently computable (wrt time) and f = o(g), then one with behavior f will also be efficiently computable (yes, I'm using imprecise language here). Similar things can be said for the other measures. In fact, small-o gives more information about the relationship of functions asymptotically than Big-O does if you consider the limit definitions of the concepts.</p>
<p>Also note that Big-O doesn't necessarily imply a &quot;tight&quot; upper bound, though we do search for such.</p>

CC BY-SA 4.0
2023-02-06T10:52:06.627Z
Thanks for the answer. I'm trying to find a practical use for little-o and little-omega that are easy for students to understand. Big-Theta I think I am able to explain as something very useful, and Big-O and Big-Omega as steps on the way to Big-Theta. But it seems to me that the "little ones" are much less intuitively or directly useful.
Thomas Padron-McCarthy
CC BY-SA 4.0
2023-02-01T23:22:02.160Z
2023-02-01T23:22:02.160Z
Buffy
<p>When analyzing asymptotic complexity of functions we have big-O, which is an upper bound. We also have big-Omega, which is a lower bound, and even though it might not seem very useful at first to have a lower bound (&quot;my program will always take longer time than this&quot;), we can use it when explaining big-Theta.</p>
<p>But how do we explain why we want the notions of small-o and small-omega? They are like big-O and big-Omega, except that they can not be tight bounds. Can we explain why we want to have bounds that are explicitly not tight?</p>

CC BY-SA 4.0
2023-02-13T10:02:25.147Z
Why do you want to teach notations for which you have no use yourself (in the course)? Teaching $O$ is sufficient to get the students familiar with asymptotic analysis. Teaching them the details of obscure notation they likely won't ever see again is a waste of time. Perhaps you could mention that $o$ and $\omega$ exist and briefly mention that they are similar to $O$ and $\Omega$ but behave more like $<$ instead of like $\leq$. That way students are aware of the existence and know where to look should they encounter the notations in the future.
Tom van der Zanden
CC BY-SA 4.0
2023-02-13T18:45:09.150Z
@TomvanderZanden: Yes, what I ended up doing with o and ω was precisely that, a very brief discussion.
Thomas Padron-McCarthy
<complexity-theory>
Why do we want small-o and small-omega?
# Why do we want small-o and small-omega?

(Asked by: username_0 on 2023-02-01)

When analyzing asymptotic complexity of functions we have big-O, which is an upper bound. We also have big-Omega, which is a lower bound, and even though it might not seem very useful at first to have a lower bound ("my program will always take longer time than this"), we can use it when explaining big-Theta.

But how do we explain why we want the notions of small-o and small-omega? They are like big-O and big-Omega, except that they can not be tight bounds. Can we explain why we want to have bounds that are explicitly not tight?

**Tags:** complexity-theory

> **Comments:**
> **username_1**: Why do you want to teach notations for which you have no use yourself (in the course)? Teaching $O$ is sufficient to get the students familiar with asymptotic analysis. Teaching them the details of obscure notation they likely won't ever see again is a waste of time. Perhaps you could mention that $o$ and $\omega$ exist and briefly mention that they are similar to $O$ and $\Omega$ but behave more like $<$ instead of like $\leq$. That way students are aware of the existence and know where to look should they encounter the notations in the future.  
> **username_0**: @TomvanderZanden: Yes, what I ended up doing with o and ω was precisely that, a very brief discussion.  

---

## 2 answers

### Answer by username_3 on 2023-02-01. Score: 3

Who is this "we" of which you speak? Note that Big-O and related concepts precedes the computational and algorithmic use. It is a concept of mathematics that is useful in analyzing the asymptotic behavior of functions: no computers need apply.

It has been applied to algorithmic analysis since the behavior of algorithms, usually, on large sets of data, can be described in mathematical (functional) terms.

See the [wikipedia article](https://en.wikipedia.org/wiki/Big_O_notation) for a discussion and comparison of the various concepts.

But to answer part of your question explicitly, if we know that a process with behavior g is efficiently computable (wrt time) and f = o(g), then one with behavior f will also be efficiently computable (yes, I'm using imprecise language here). Similar things can be said for the other measures. In fact, small-o gives more information about the relationship of functions asymptotically than Big-O does if you consider the limit definitions of the concepts.

Also note that Big-O doesn't necessarily imply a "tight" upper bound, though we do search for such.

> **Comments:**
> **username_0**: Thanks for the answer. I'm trying to find a practical use for little-o and little-omega that are easy for students to understand. Big-Theta I think I am able to explain as something very useful, and Big-O and Big-Omega as steps on the way to Big-Theta. But it seems to me that the "little ones" are much less intuitively or directly useful.  

---

### Answer by username_2 on 2023-02-07. Score: 1

If you want to see if a number is prime naively you try all of its potential factors. A little more cleverness shows that `sqrt(n)` factors are enough.

One of the best methods is the Quadratic Sieve, which takes `exp( sqrt( ln n lnln n ))` which is `o(sqrt(n))`.

<https://mathworld.wolfram.com/QuadraticSieve.html>

I know that you can't teach the quadratic sieve to your students, but they will understand the complexity of the naive algorithm, and that it start taking lots of time for large numbers: just code it out. Now "little-oh" means that for n large enough this is more than 5 times as fast. And for even larger n it's 50 times as fast. And for much much larger n it's 500 times as fast. Et cetera.

So big-oh tells you how fast an algorithm is, little-oh tells you that it's essentially faster than another algorithm.


---

