-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$

closed as too broad by D.W., Gamow, Sasho Nikolov, Jeffε, Jan Johannsen Aug 6 '18 at 7:35

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$
  • $\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.