<p>The Sieve of Erathosthenes to find all primes up to $n$ is perhaps the best-known example of an $O(n \log \log n)$ algorithm:</p>

<p><a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noreferrer">https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes</a></p>

<p>Its running time is $O(n \cdot \sum_{p \le n} \frac{1}{p})$ (where the sum ranges over primes $P$), which is $O(n \log \log n)$ by Merten's second theorem:</p>

<p><a href="https://en.wikipedia.org/wiki/Mertens%27_theorems" rel="noreferrer">https://en.wikipedia.org/wiki/Mertens%27_theorems</a></p>

CC BY-SA 4.0
2018-08-03T05:55:55.697Z
By a slight modification, you can also use it to find smooth numbers, and it's used this way in state-of-the-art factorization algorithms like GNFS! (Smooth numbers have all their factors below some small limit, where the definition of "small" is problem-dependent).
Elliot Gorokhovsky
CC BY-SA 4.0
2018-08-03T05:58:38.637Z
Also, I should add that the Sieve of Erasthosthenes actually has complexity $O(n \log n \log \log n)$ in the RAM model. The number of *additions* is $O(n \log \log n)$, but the complexity of each addition is $O(\log n)$. So your result is only true in the arithmetic model of computation, though it's a very minor nitpick.
Elliot Gorokhovsky
CC BY-SA 4.0
2018-08-01T16:57:26.950Z
2018-08-02T23:26:48.700Z
2018-08-02T23:26:48.700Z
david
<p>Interpolation search has expected $O(\log\log n)$ time complexity under the assumption that the keys are uniformly distributed:
<a href="http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf" rel="nofollow noreferrer">http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf</a></p>

CC BY-SA 4.0
2018-07-31T19:33:09.250Z
2018-07-31T19:33:09.250Z
Aryeh
<p><strong>Evergreen disclaimer</strong>: I might be missing something.</p>

<p>(This was a response to the question when OP had a typo that said $O(\log \log n)$ running time, rather than $O(n \log \log n)$. I guess I'll leave it here.)</p>

<p>The answer to this problem is "there's nothing interesting unless you specify a non-standard model."</p>

<p>Notice that it's quite delicate to talk about classes with running time o(n), since for such small running times, the model of computation matters quite a bit. E.g., binary search is a $O(\log n)$-time algorithm in some RAM models, $O(\log^2 n)$-time in other RAM models, and $\widetilde{O}(n)$ in the Turing Machine model.</p>

<p>This problem gets much worse for $o(\log n)$-time algorithms. For example, RAM models often allow us to write down the $O(\log n)$-length address of a bit (e.g., an input bit) for free (this is the model in which we typically think of, say, binary search), but if we're aiming for $o(\log n)$ time, then this seems rather unfair. And, if we don't have the ability to even specify a bit that we'd like to look at, what use is a RAM?</p>

<p>More generally, it's rather strange to have a running time that depends on a parameter $n$ that we can't even write down! For this reason, I imagine that one could prove that the only problems with $o(\log n)$-time algorithms in "most reasonable models" fall into two classes:</p>

<ol>
<li>problems that only depend on the first $O(1)$ input bits (e.g., "do the first 10 bits of the input represent a prime number?"), </li>
<li>promise problems with "very strong promises" (e.g., "under the promise that the first sequence of three consecutive zeros appears in the first $o(\log n)$ bits of the input, is there a sequence of twenty consecutive ones before the first consecutive zeros?").</li>
</ol>

<p>There are of course models where it does make sense to talk about such low "running times" and even $O(1)$ "running times," but typically what we actually mean by the "running time" here is really a different complexity measure--usually some kind of oracle queries. E.g., Aryeh linked to a paper in which the complexity measure is the number of file accesses in a certain model.</p>

CC BY-SA 4.0
2018-08-01T02:40:13.130Z
2018-08-01T15:53:38.953Z
2018-08-01T15:53:38.953Z
Noah Stephens-Davidowitz
<p>I am looking for the list of problems with runtime $O(n\log \log n)$, where $n$ is the size of the input. I tried to search on internet but did not able to find any.</p>

CC BY-SA 4.0
2018-07-31T21:59:17.103Z
Not sure how this is a valid research-level question. Why would such a list exist? Are you looking for "natural" problems? If so, for which notion of "natural"?
Clement C.
CC BY-SA 4.0
2018-08-01T06:46:59.987Z
Sorry for the misunderstanding. I forget to put $n$ initally. I have edited the question.
lovw
CC BY-SA 4.0
2018-08-01T09:45:32.893Z
I don't think this is an appropriate question. You could pick any random running time bound and ask for such a list. Why should we care?
Sasho Nikolov
CC BY-SA 4.0
2018-08-01T11:47:48.057Z
First time I've seen the question it was asking for $\log\log$  running time now it changed to $n \log\log$ I'm afraid the next time it changes to $n^2 \log\log n$ or any other strange running time. Sounds like a homework question.
Saeed
CC BY-SA 4.0
2018-08-01T16:29:56.657Z
I thought it was more interesting with the log log n.
Aryeh
<soft-question>
Algorithms with run-time $O(n\log \log n)$
lovw
# Algorithms with run-time $O(n\log \log n)$

(Asked by: username_0 on 2018-07-31)

I am looking for the list of problems with runtime $O(n\log \log n)$, where $n$ is the size of the input. I tried to search on internet but did not able to find any.

**Tags:** soft-question

> **Comments:**
> **username_1**: Not sure how this is a valid research-level question. Why would such a list exist? Are you looking for "natural" problems? If so, for which notion of "natural"?  
> **username_0**: Sorry for the misunderstanding. I forget to put $n$ initally. I have edited the question.  
> **username_2**: I don't think this is an appropriate question. You could pick any random running time bound and ask for such a list. Why should we care?  
> **username_3**: First time I've seen the question it was asking for $\log\log$  running time now it changed to $n \log\log$ I'm afraid the next time it changes to $n^2 \log\log n$ or any other strange running time. Sounds like a homework question.  
> **username_4**: I thought it was more interesting with the log log n.  

---

## 3 answers

### Answer by username_5 on 2018-08-01. Score: 11

The Sieve of Erathosthenes to find all primes up to $n$ is perhaps the best-known example of an $O(n \log \log n)$ algorithm:

<https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>

Its running time is $O(n \cdot \sum\_{p \le n} \frac{1}{p})$ (where the sum ranges over primes $P$), which is $O(n \log \log n)$ by Merten's second theorem:

<https://en.wikipedia.org/wiki/Mertens%27_theorems>

> **Comments:**
> **username_6**: By a slight modification, you can also use it to find smooth numbers, and it's used this way in state-of-the-art factorization algorithms like GNFS! (Smooth numbers have all their factors below some small limit, where the definition of "small" is problem-dependent).  
> **username_6**: Also, I should add that the Sieve of Erasthosthenes actually has complexity $O(n \log n \log \log n)$ in the RAM model. The number of *additions* is $O(n \log \log n)$, but the complexity of each addition is $O(\log n)$. So your result is only true in the arithmetic model of computation, though it's a very minor nitpick.  

---

### Answer by username_4 on 2018-07-31. Score: 4

Interpolation search has expected $O(\log\log n)$ time complexity under the assumption that the keys are uniformly distributed:
<http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf>


---

### Answer by username_7 on 2018-08-01. Score: 4

**Evergreen disclaimer**: I might be missing something.

(This was a response to the question when OP had a typo that said $O(\log \log n)$ running time, rather than $O(n \log \log n)$. I guess I'll leave it here.)

The answer to this problem is "there's nothing interesting unless you specify a non-standard model."

Notice that it's quite delicate to talk about classes with running time o(n), since for such small running times, the model of computation matters quite a bit. E.g., binary search is a $O(\log n)$-time algorithm in some RAM models, $O(\log^2 n)$-time in other RAM models, and $\widetilde{O}(n)$ in the Turing Machine model.

This problem gets much worse for $o(\log n)$-time algorithms. For example, RAM models often allow us to write down the $O(\log n)$-length address of a bit (e.g., an input bit) for free (this is the model in which we typically think of, say, binary search), but if we're aiming for $o(\log n)$ time, then this seems rather unfair. And, if we don't have the ability to even specify a bit that we'd like to look at, what use is a RAM?

More generally, it's rather strange to have a running time that depends on a parameter $n$ that we can't even write down! For this reason, I imagine that one could prove that the only problems with $o(\log n)$-time algorithms in "most reasonable models" fall into two classes:

1. problems that only depend on the first $O(1)$ input bits (e.g., "do the first 10 bits of the input represent a prime number?"),
2. promise problems with "very strong promises" (e.g., "under the promise that the first sequence of three consecutive zeros appears in the first $o(\log n)$ bits of the input, is there a sequence of twenty consecutive ones before the first consecutive zeros?").

There are of course models where it does make sense to talk about such low "running times" and even $O(1)$ "running times," but typically what we actually mean by the "running time" here is really a different complexity measure--usually some kind of oracle queries. E.g., username_4 linked to a paper in which the complexity measure is the number of file accesses in a certain model.


---

