3
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ I don't think there is a universally agreed upon definition of near-linear time. $\endgroup$ 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$ 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$ 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$ Sep 30 '16 at 20:57
8
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ Even $\varepsilon > 1$? $\endgroup$
    – ov7a
    Oct 2 '16 at 20:08
  • 2
    $\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$ 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$ Jul 28 '20 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.