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$ Sep 30, 2016 at 17:55
  • $\begingroup$ Why do you think so? $\endgroup$
    – ov7a
    Sep 30, 2016 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, 2016 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, 2016 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, 2016 at 20:57

1 Answer 1


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

  • 4
    $\begingroup$ Even $\varepsilon > 1$? $\endgroup$
    – ov7a
    Oct 2, 2016 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, 2016 at 0:20
  • 1
    $\begingroup$ We can note that this definition includes the family of algorithms in $O\big(n.log(n)\big)$. $\endgroup$
    – ebonnal
    Jul 28, 2020 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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