<p>A natural definition of <em>"near-linear"</em> should be:</p>

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

CC BY-SA 3.0
2016-10-02T20:08:40.373Z
Even $\varepsilon > 1$?
ov7a
CC BY-SA 3.0
2016-10-04T00:20:13.290Z
@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$.
Ivan Smirnov
CC BY-SA 4.0
2020-07-28T13:58:25.237Z
We can note that this definition includes the family of algorithms in $O\big(n.log(n)\big)$.
ebonnal
CC BY-SA 3.0
2016-10-01T16:31:38.377Z
2016-10-01T16:31:38.377Z
Gamow
<p>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.</p>

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

CC BY-SA 3.0
2016-09-30T17:55:58.310Z
I don't think there is a universally agreed upon definition of near-linear time.
Yuval Filmus
CC BY-SA 3.0
2016-09-30T18:05:18.443Z
Why do you think so?
ov7a
CC BY-SA 3.0
2016-09-30T18:07:18.043Z
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)})$.
Yuval Filmus
CC BY-SA 3.0
2016-09-30T18:13:45.433Z
May be there is some survey related to this topic? What is the common way to deal with such algorithms if strict complexity estimate is required (in your field)? Upper bound?
ov7a
CC BY-SA 3.0
2016-09-30T18:15:24.417Z
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)$).
Yuval Filmus
CC BY-SA 3.0
2016-09-30T20:57:04.697Z
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)})$
Sasho Nikolov
CC BY-SA 4.0
2023-09-08T17:41:45.767Z
Related: https://cs.stackexchange.com/questions/152856/difference-between-almost-linear-and-quasilinear-time-complexities which distinguishes "almost linear" (what Gamow's answer calls "near-linear"), and "quasilinear" (O(n polylog n))
Antoine Amarilli 'a3nm'
<time-complexity><definitions>
Definition of near-linear algorithm
ov7a
# Definition of near-linear algorithm

(Asked by: username_0 on 2016-09-30)

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.

**Tags:** time-complexity, definitions

> **Comments:**
> **username_1**: I don't think there is a universally agreed upon definition of near-linear time.  
> **username_0**: Why do you think so?  
> **username_1**: 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)})$.  
> **username_0**: May be there is some survey related to this topic? What is the common way to deal with such algorithms if strict complexity estimate is required (in your field)? Upper bound?  
> **username_1**: 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)$).  
> **username_2**: 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)})$  
> **username_3**: Related: https://cs.stackexchange.com/questions/152856/difference-between-almost-linear-and-quasilinear-time-complexities which distinguishes "almost linear" (what username_4's answer calls "near-linear"), and "quasilinear" (O(n polylog n))  

---

## 1 answers

### Answer by username_4 on 2016-10-01. Score: 8

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

> **Comments:**
> **username_0**: Even $\varepsilon > 1$?  
> **username_5**: @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$.  
> **username_6**: We can note that this definition includes the family of algorithms in $O\big(n.log(n)\big)$.  

---

