Question

Brief:
When academic (computer science) papers say "O(polylog(n))", what do they mean? I m not confused by the "Big-Oh" notation, which I m very familiar with, but rather by the function polylog(n). They re not talking about the complex analysis function Li_s(Z) I think. Or are they? Something totally different maybe?

More detail:
Mostly for personal interest, I ve recently been looking over various papers on Compressed Suffix Arrays, e.g. Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays. The computational complexity estimates stated sometimes involve polylog(n), which is a function I m not familiar with.

Wikipedia gives a definition of polylog_s(z) which appears to mainly be about complex analysis and analytic number theory. My suspicion is that it s not related to the polylog(n) in the compression papers, though I d love to hear otherwise from someone more knowledgeable. If this is the case, why exactly is it thought reasonable to omit the subscript?

My only other guess is that maybe O(polylog(n)) is supposed to mean "Asymptotic to a polynomial function of log(n)." But that s only a guess: I have no evidence of this, and it would be an abuse of notation to boot.

In any case, a link to a reasonably authoritative definition would be greatly appreciated!

Answer 1

Abuse of notation or not, polylog(n) does mean "some polynomial in log(n)", just as "poly(n)" can mean "some polynomial in n". So O(polylog(n)) means "O((log n)^k) for some k". (See Wikipedia: Polylogarithmic, or, to see it in context, Prof. Scott Aaronson s blog: My Favorite Growth Rates.)

The point is that just as we often don t care about constant factors, it is often convenient to ignore powers of logarithms. Sometimes the "log factors" are ignored entirely and you might see "Õ(f(n))" — O with a tilde above it — which means "O(f(n) polylog(f(n)))", i.e., "O(f(n) (log f(n))^k) for some k".

Answer 2

The way it is used in this paper seems to be describing something as:

O(log^p n)

Answer 3

Polylog(n) is just "polynomial in the log of n". Wikipedia

Answer 4

Different polylog article. You re guess is pretty close.

Answer 5

Wolfram gives you a selection, of which the polylogarithm page looks most promising.

友情链接