Running times comparison

Question

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?

Answer 1

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

Answer 2

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