Definition of near-linear algorithm
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&gt;0$.