10
$\begingroup$

Is there a complexity degree that is bigger than $O(n)$ and smaller than $O(n \log n)$?

$\endgroup$

closed as off-topic by Christian Clason, Geoffrey Irving, Geoff Oxberry Jun 2 '14 at 21:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "General computer science questions are off-topic here, but can be asked on Computer Science Stack Exchange." – Christian Clason, Geoffrey Irving, Geoff Oxberry
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ I think perhaps this question would fit better in the Computer Science stackexchange? $\endgroup$ – LKlevin Jun 2 '14 at 10:06
  • $\begingroup$ @LKlevin: Agreed. $\endgroup$ – Geoff Oxberry Jun 2 '14 at 21:23
  • 2
    $\begingroup$ The computer science stack exchange is not very friendly towards basic questions like this. $\endgroup$ – Nick Alger Dec 9 '14 at 5:44
20
$\begingroup$

$n \log\log n$ is between $n$ and $n \log n$, and is a relatively common one to find in the wild.

$\endgroup$
  • 5
    $\begingroup$ For example, the sieve of Erasthenos has a complexity of $O(n \log \log n)$. $\endgroup$ – Eamon Nerbonne Jun 1 '14 at 14:38
  • 1
    $\begingroup$ Though, depending on the motivation of the asker this may not be relevant distinction - for all practical purposes $\log \log n$ is just a small constant factor. $\endgroup$ – Eamon Nerbonne Jun 1 '14 at 14:39
  • 2
    $\begingroup$ Yeah, though that's true for for $\log n$ as well if $n$ is small enough! $\endgroup$ – Bill Barth Jun 1 '14 at 15:07
  • 1
    $\begingroup$ @BillBarth Yes, but it's exponentially less constant than the $\log \log n$ constant! $\endgroup$ – Pål GD Jun 1 '14 at 18:16
7
$\begingroup$

On top of $O(n\log(\log(n)))$, there's also $O(n \log^*(n))$ in which $\log^*$ is the number of times the logarithm function must be applied in order for the result to be less than or equal to 1.

For instance, if you already know an Euclidean minimum spanning tree, the Delaunay triangulation may be discovered in $O(n\log^*(n))$ time.

More extremely, one can look at the inverse Ackermann function $\alpha(n,n)$, which may be found in the analysis of several algorithms of complexity $O(n\alpha(n,n))$. There's a good introduction here.

$\endgroup$
  • 2
    $\begingroup$ Don't forget the glory that is $\alpha^*(n)$, the iterated inverse ackermann function! $\endgroup$ – Alexis Beingessner Jun 1 '14 at 17:50
4
$\begingroup$

There are infinitely many, since $O(n(\log n)^\alpha) \subsetneq O(n(\log n)^\beta)$ for any $\alpha<\beta$. So, in particular, $O(n) = O(n(\log n)^0) \subsetneq O(n(\log n)^\alpha) \subsetneq O(n\log n)$ for any $\alpha\in (0,1)$.

$\endgroup$

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