Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to find which of following algorithms has the smallest running time:

1) $O\left(\sqrt{q}\cdot\operatorname{polylog}(q)\right)$; is that linearithmic?

2) $O\left(\operatorname{polylog}(q)\cdot\max\{\sqrt{p}\}\right)$; is that linearithmic?

3) $2^{O\left(\sqrt{n \log(n)}\right)}$; is that polynomial?

Can you help me?

share|cite|improve this question
I've made an attempt to improve the formatting. I don't know what "linearithmic" means. I don't know what $\max\sqrt p$ means. – Gerry Myerson Dec 11 '11 at 21:31
@Gerry: Linearithmic is $O(n\log n)$. I don’t understand what the maximum is taken over either. – Brian M. Scott Dec 11 '11 at 21:34
@GerryMyerson Thanks for the formatting! maxp√p is just the largest element of a set! – mixkat Dec 11 '11 at 21:40
Yes, but which set? – Gerry Myerson Dec 11 '11 at 21:41
@GerryMyerson Doesnt really matter...Suppose that you apply the algorithms to the same set and all of them use p in their computation but only the running time of (2) depends on that! – mixkat Dec 11 '11 at 21:45

(1) Try to show that $(\log q)^n$ is $O(\sqrt q)$.

(2) I don’t understand what you’re maximizing over, or how $p$ and $q$ are related.

(3) Look at a really simple example: $2^\sqrt{n}$. Is that polynomial?

share|cite|improve this answer

$2^{\sqrt{n\log n}}$ grows faster than any polynomial.

Polylogarithmic means polynomial in the logarithm. Any function that is $O(\sqrt qf(q))$ where $f$ is polylogarithmic, is also linearithmic.

The one with $\max\sqrt p$, we'd have to know the set over which we're taking the maximum in order to make any sense of this.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.