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

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?

• I don't think that there are formal definitions. But why would that matter ?
– user16034
Jul 8, 2022 at 11:52

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

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

• $$0.
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 as a family of functions that "differentiates" between "almost-linear" functions and quasilinear functions.