Is there a complexity degree that is bigger than $O(n)$ and smaller than $O(n \log n)$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ I think perhaps this question would fit better in the Computer Science stackexchange? $\endgroup$– LKlevinJun 2, 2014 at 10:06
-
$\begingroup$ @LKlevin: Agreed. $\endgroup$– Geoff OxberryJun 2, 2014 at 21:23
-
2$\begingroup$ The computer science stack exchange is not very friendly towards basic questions like this. $\endgroup$– Nick AlgerDec 9, 2014 at 5:44
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
$n \log\log n$ is between $n$ and $n \log n$, and is a relatively common one to find in the wild.
answered Jun 1, 2014 at 13:49
-
5$\begingroup$ For example, the sieve of Erasthenos has a complexity of $O(n \log \log n)$. $\endgroup$ Jun 1, 2014 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$ Jun 1, 2014 at 14:39
-
2$\begingroup$ Yeah, though that's true for for $\log n$ as well if $n$ is small enough! $\endgroup$ Jun 1, 2014 at 15:07
-
1$\begingroup$ @BillBarth Yes, but it's exponentially less constant than the $\log \log n$ constant! $\endgroup$– Pål GDJun 1, 2014 at 18:16
$\begingroup$
$\endgroup$
1
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.
-
2$\begingroup$ Don't forget the glory that is $\alpha^*(n)$, the iterated inverse ackermann function! $\endgroup$ Jun 1, 2014 at 17:50
$\begingroup$
$\endgroup$
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)$.
