Hacker News Reader

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.

View on HN

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.

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.)

Oh, so it is. I retract my comment. In that case it seems like a pretty stupid designation to me.

Reply on news.ycombinator.com