News for hackers. Stuff that matters.
Re:Researchers achieve ‘absurdly fast’ algorithm for network... by mauricioc on Thursday June 09, 2022 @04:52AM (#31679008)
log(log(m))/log(m) tends to zero as m tends to infinity, which is what it means to be o(1). It is decreasing for m > e^e.

Besides n^(1+o(1)), the other common definition for "almost linear" is precisely O(n log^k (n)) for some k, no matter how large.

Re:Researchers achieve ‘absurdly fast’ algorithm for network... by lkozma on Thursday June 09, 2022 @05:57AM (#31679351)
Your first point is correct, but just to clarify your second point, these two definitions are not quite equivalent, as there is a world of functions growing more quickly than log^k(n) no matter how large constant k, but still within n^o(1).

For an example, consider 2^sqrt(log(n)).

This is a bit similar to something being faster than polynomial, but slower than exponential.

Re:Researchers achieve ‘absurdly fast’ algorithm for network... by mauricioc on Thursday June 09, 2022 @09:53AM (#31681141)
Thanks for the clarification! I didn't mean to say the two definitions were equivalent, as indeed they aren't. Rephrasing my second point to (hopefully) eliminate the ambiguity: There are two non-equivalent popular definitions for "almost linear" or "nearly linear" (n^(1+o(1)) and O(n log^k(n)), and nevertheless classifying "n log^1000 n" as almost linear is uncontroversial in the sense that both of the common definitions do it.

(The second paragraph of my original message addressed a point made in the parent's second paragraph, which has since been edited out.)

Re:Researchers achieve ‘absurdly fast’ algorithm for network... by Jweb_Guru on Thursday June 09, 2022 @05:09AM (#31679120)
Oh, so it is. I retract my comment. In that case it seems like a pretty stupid designation to me.