0
$\begingroup$

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?

  • 1
    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.2011-12-11
  • 1
    @Gerry: Linearithmic is $O(n\log n)$. I don’t understand what the maximum is taken over either.2011-12-11
  • 0
    @GerryMyerson Thanks for the formatting! maxp√p is just the largest element of a set!2011-12-11
  • 1
    Yes, but which set?2011-12-11
  • 0
    @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!2011-12-11
  • 0
    I'm sorry, that makes no sense to me.2011-12-11

2 Answers 2

1

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

0

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