0
$\begingroup$

If there is an algorithm with time complexity $O(n^{n/log(n)})$, is that already exponential time or still subexponential time?

It shouldn't be considered quasi-polynomial since the exponent is also depending on $n$, right?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

$$n^{\tfrac{n}{\log_2 n}} = (2^{\log_2 n})^{\tfrac{n}{\log_2 n}} = 2^{\tfrac{n}{\log_2 n}\times \log_2 n} = 2^n$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, maybe I should have put a little bit more thought to it :P $\endgroup$
    – user154939
    Commented Dec 11, 2022 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.