There are quite a lot papers describing near-linear algorithms. They are usually iterative, with linear complexity of one iteration. Others have $O(n\log^k n)$ time compexity.

I'm failed to find a decent source with the definition of "near-linear" time, which covers both types. Please, help me find one.

  • 3
    $\begingroup$ I don't think there is a universally agreed upon definition of near-linear time. $\endgroup$ – Yuval Filmus Sep 30 '16 at 17:55
  • $\begingroup$ Why do you think so? $\endgroup$ – ov7a Sep 30 '16 at 18:05
  • 3
    $\begingroup$ I have never heard of the concept, so it can't be universally agreed upon. In my field there is a similar concept, quasilinear, which could mean $O(n\log^{O(1)}n)$, or perhaps $O(n^{1+o(1)})$. $\endgroup$ – Yuval Filmus Sep 30 '16 at 18:07
  • 3
    $\begingroup$ It is much better to use an explicit upper bound rather than some term which means different things to different people, unless you explain what you mean by the term. We do use $\tilde O$ notation, which usually means "up to logarithmic terms" (i.e. $\tilde O(n) = O(n\log^{O(1)}n)$). $\endgroup$ – Yuval Filmus Sep 30 '16 at 18:15
  • 4
    $\begingroup$ Near linear time is not a formal term usually, so, like Yuval said, you should check the papers for what they mean exactly. Usually, the meaning is either $O(n \log^{O(1)} n)$ (as in the nearly linear time Laplacian solvers and algorithms that use them, and the nearly linear time PTAS for TSP and related algorithms), or, less often $O(n^{1 + o(1)})$ $\endgroup$ – Sasho Nikolov Sep 30 '16 at 20:57

A natural definition of "near-linear" should be:

A function $f:\mathbb{N}\to\mathbb{N}$ is near-linear, if $~f(n)\in O(n^{1+\varepsilon})~$ for all $\varepsilon>0$.

| cite | improve this answer | |
  • 2
    $\begingroup$ Even $\varepsilon > 1$? $\endgroup$ – ov7a Oct 2 '16 at 20:08
  • 1
    $\begingroup$ @ChelovekChelovechnii It is crucial that $\varepsilon$ can be arbitrarily small, large epsilons do not matter. If $f(n) \in O(n^{1+0.5})$ then obviously $f(n) \in O(n^{1+\varepsilon})$ for all $\varepsilon > 1$. $\endgroup$ – Ivan Smirnov Oct 4 '16 at 0:20
  • $\begingroup$ We can note that this definition includes the family of algorithms in $O\big(n.log(n)\big)$. $\endgroup$ – EnzoBnl Jul 28 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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