What is the complexity class of an algorithm that runs in $n^{\mathcal{O}(\sqrt{n}log(n))}$ time?

As $n$ gets large $\sqrt{n}log(n)$ increases at a very slow rate. Does this mean that the algorithm has the same complexity as $n^{\mathcal{O}(1)}$, which would be in $P$?


No, $\sqrt{n}$ increases far faster than $O(1)$, and $n^{\sqrt{n}}$ grows far faster than $n^{O(1)}$. No, it certainly does not have the same runtime. See Sorting functions by asymptotic growth.

There may be no predefined complexity class; the complexity class is the class of all algorithms who run in time $n^{O(\sqrt{n} \log n)}$, and there's probably not much more to say.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your response. Just to be clear, your saying it's inconclusive whether this is in $P$ or Sharp-$P$, right? $\endgroup$ – Teferi Mar 27 at 13:33
  • 1
    $\begingroup$ @Teferi, I was saying nothing about that - you didn't ask. It's certainly not in P. $\endgroup$ – D.W. Mar 27 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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