-2
$\begingroup$

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.

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

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

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$ – Elliot Gorokhovsky Aug 3 '18 at 5:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Elliot Gorokhovsky Aug 3 '18 at 5:58
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.