# Algorithms with run-time $O(n\log \log n)$ [closed]

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.

• 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"? Jul 31 '18 at 21:59
• Sorry for the misunderstanding. I forget to put $n$ initally. I have edited the question.
– lovw
Aug 1 '18 at 6:46
• 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? Aug 1 '18 at 9:45
• 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. Aug 1 '18 at 11:47
• I thought it was more interesting with the log log n. Aug 1 '18 at 16:29

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

• 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). Aug 3 '18 at 5:55
• 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. Aug 3 '18 at 5:58

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

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., Aryeh linked to a paper in which the complexity measure is the number of file accesses in a certain model.