What is the meaning of O( polylog(n) )? In particular, how is polylog(n) defined?
AlgorithmFull Text-SearchCompressionComplexity TheoryAlgorithm Problem Overview
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 https://en.wikipedia.org/wiki/Polylogarithm">Li<sub>s</sub>(Z)</a> 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. https://link.springer.com/chapter/10.1007/978-3-540-30551-4_59?from=SL">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 https://en.wikipedia.org/wiki/Polylogarithm">polylog<sub>s</sub>(z)</a> 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!
Algorithm Solutions
Solution 1 - Algorithm
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 http://en.wikipedia.org/wiki/Polylogarithmic">Wikipedia: Polylogarithmic, or, to see it in context, Prof. Scott Aaronson's blog: http://scottaaronson.com/blog/?p=263">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 http://en.wikipedia.org/wiki/%C3%95">means</a> "O(f(n) polylog(f(n)))", i.e., "O(f(n) (log f(n))k) for some k".
Solution 2 - Algorithm
The way it is used in this paper seems to be describing something as:
O(log^p n)
Solution 3 - Algorithm
Polylog(n) is just "polynomial in the log of n". Wikipedia
Solution 4 - Algorithm
Different polylog article. You're guess is pretty close.
Solution 5 - Algorithm
I'm sure they mean only the positive integer real axis: Re(n) = n
Solution 6 - Algorithm
Wolfram gives you a selection, of which the polylogarithm page looks most promising.