Difference between "almost-linear" and "quasilinear" time complexities

Question

In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$.

This is similar to the notion of quaslinear complexity, which refers to a complexity of $O(n \log^{O(1)} n)$.

It is clear that quasilinear complexity is a subset of "almost-linear" complexity. However, I am unable to find an example of a complexity which is "almost-linear" yet not quasilinear. What is the differentiating factor between these two complexities?

Answer 1

Let $f_a(n)=n^{1+(\log n)^{-a}}$, where $a\ge0$.

• $a=0$.
  $f_0(n)=n^2$ is not "almost-linear".

• $0<a<1$.
  Since $(\log n)^{-a}=o(1)$, $f_a(n)$ is almost-linear.

  For any constant $c$,

  $$\begin{aligned} \lim_{n\to\infty}\frac{f_a(n)}{n(\log n)^c} &=\lim_{n\to\infty}\frac{n^{(\log n)^{-a}}}{(\log n)^c}\\ &=\lim_{n\to\infty}\frac{\left(e^{\log n}\right)^{(\log n)^{-a}}} {\left(e^{\log\log n}\right)^c}\\ &=\lim_{n\to\infty}e^{(\log n)^{1-a}-c\log\log n}\\ &=\lim_{m\to\infty}e^{m^{1-a}-c\log m}\\ &=\infty\\ \end{aligned}$$

  So, $f_a(n)$ is not quasilinear.

• $a = 1$.
  $f_1(n)=en$ is quasilinear, where $e$ is Euler's number.

We can view $f_a$ where $0<a<1$ as a family of functions that "differentiates" between "almost-linear" functions and quasilinear functions.