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