Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Learn more about Collectives

Teams

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Learn more about Teams

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!

In the linked abstract, it is stated "... the CSA can be searched in O(m) time whenever = O(polylog(n))." – Managu Nov 26, 2009 at 1:57

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".

it is often convenient to ignore powers of logarithms Strange. How can ignoring powers of logarithms be convenient, when it changes meaning altogether? – Lazer Apr 6, 2010 at 5:56 @eSKay: The same way it is often convenient to ignore constant factors even though it changes meaning altogether — it just depends on what you want to focus on. Any polylogarithmic function grows slower than O(n^ε) for every ε. So when what you care about is the exponent in n — e.g. trying to distinguish between n^2.1 and n^2 — these polylog factors don't matter. O(n^2 polylog(n)) is O(n^(2+ε)) for all ε, so we write Õ(n^2). – ShreevatsaR Apr 6, 2010 at 14:17 @ShreevatsaR I found your answer really helpful in understanding the Master Theorem for solving recurrences – Geek Aug 3, 2012 at 7:47 So it should probably be written as O(poly(log n)) , and then it's clear! O(polylog(n)) is confusing. – Tomas Dec 25, 2013 at 18:22 @Tomas: Yes that might have helped. In this case the word "polylogarithmic" was already in use before the O() notation became widespread, so "polylog" is an abbreviation for "polylogarithmic", rather than being made up from scratch from notation as "poly(log)" (which as you say might have been clearer). – ShreevatsaR Dec 26, 2013 at 2:52

Thanks for contributing an answer to Stack Overflow!

• Please be sure to answer the question . Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.
• Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers .