Wrong use of asymptotic notation in the Multi-dimensional Arrays page

I’m learning Julia and, reading the documentations in the past days, I wrote down few comments on typos, unclear sentences, etc. I’m new to the community and I’m unsure whether I should directly open an issue on GitHub, and/or create a pull request.

For example, in the third sentence of the second paragraph of the Implementation section of the Multi-dimensional Arrays documentation page it is written

It is recommended that these operations have nearly constant time complexity, or technically Õ(1) complexity, as otherwise some array functions may be unexpectedly slow.

AFAIK, Õ(1) is quite an abuse of notation, since \tilde O(f(n)) := O(f(n)\textrm{polylog}(f(n))), that is O(f(n)) up to polylogarithms of f(n) (see e.g. Wikipedia), while here it is used as if it meant up to polylogarithms of n.

I do think it should say O(\text{polylog}(n)) or \cup_{\epsilon > 0} O(n^\epsilon) to be clearer, and to be honest this is the first time seeing the soft O notation, so I am not as certain if it is commonly used.

I guess you mean \cap_{\epsilon>0} O(n^\epsilon), which I would call sub-polynomial, where with polynomial I refer to any function of the form n^c with c>0 (the latter terminology is customary in theoretical computer science, AFAIK). However, I think that here nearly-constant means at most polylogarithmic.

Perhaps I should open a pull request where I propose to remove the Õ(1), and avoid proposing to substitute it with something else.

I don’t know that there’s a true standard across the community, but my general impression is that issues are fine, but if there’s an obvious and concrete fix, and you’re willing to make the PR, just go for it. If there’s a CONTRIBUTING.md, read that first, just in case.

The only time I’d say it might be better to lead with an issue is if the fix will take a lot of effort, and you’re not sure that the fix is actually desired by the package maintainers.


compare Polylogarithm function:

with polynomial in the logarithm:

it would be good if you’re changing the docs not to make that confusion.