2
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.