title: What is the meaning of O( polylog(n) )? In particular, how is polylog(n) defined?
body: <p><b>Brief:</b><br/>
  When academic (computer science) papers say &quot;O(polylog(n))&quot;, what do they mean?  I'm not confused by the &quot;Big-Oh&quot; notation, which I'm very familiar with, but rather by the function polylog(n).  They're not talking about the complex analysis function <a href="https://en.wikipedia.org/wiki/Polylogarithm" rel="noreferrer">Li<sub>s</sub>(Z)</a> I think. Or are they?  Something totally different maybe?</p>
  <p><b>More detail:</b><br/>
  Mostly for personal interest, I've recently been looking over various papers on Compressed Suffix Arrays, e.g. <a href="https://link.springer.com/chapter/10.1007/978-3-540-30551-4_59?from=SL" rel="noreferrer">Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays</a>.  The computational complexity estimates stated sometimes involve polylog(n), which is a function I'm not familiar with.</p>
  <p>Wikipedia gives a definition of <a href="https://en.wikipedia.org/wiki/Polylogarithm" rel="noreferrer">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?</p>
  <p>My only other guess is that maybe O(polylog(n)) is supposed to mean &quot;Asymptotic to a polynomial function of log(n).&quot;  But that's only a guess:  I have no evidence of this, and it would be an abuse of notation to boot.</p>
  <p>In any case, a link to a reasonably authoritative definition would be greatly appreciated!</p>