# Running times comparison

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?

-
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?

-

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

-