3 ms·
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 mor
by lkozma 4y ago
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.
- mauricioc 4y agoThanks 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.)