Assuming a problem has complexity $O(3^{n/3})$,

Which is its class of complexity ?

Despite that it is not as $2^{n}$ ,we can say is an exponential ?

  • 1
    $\begingroup$ There was no complexity in the original formulation of the question, only pure mathematics about asymptotic classes. I artificially introduced complexity so as not to keep your intended meaning, but the question was badly worded. $\endgroup$ – babou Dec 21 '14 at 11:14

Yes, that is exponential. Something is exponential if it is $2^{O(n^k)}$ for some $k$. You can write $3^{n/3}$ as $2^{n\frac{\log 3}{3 \log 2}}$, so it fits.

It would be more common to write $(3^{1/3})^n \approx 1.44^n$.

  • $\begingroup$ Answer is almost OK, but you should not accept a math question as a complexity question when there is no apparent complexity in it. Also, it is nice to parenthesize exponentials to avoid reading errors. You assumed left associativity, but the usual reading of exponentials is right associativity. So $3^{{1/3}^n}= 3^{({1/3}^n)}$, which is a double exponential, actually decreasing with $n$, which is rather unusual for a complexity measure. $\endgroup$ – babou Dec 21 '14 at 11:33
  • 1
    $\begingroup$ $3^{(1/3)^n} \neq 3^{n/3}$. $\endgroup$ – David Richerby Dec 21 '14 at 11:41
  • $\begingroup$ Oh, the penny just dropped. Now I understand what you meant and understand @babou's comment. I've edited the answer to correct it. Remember that $x^{y^z}$ means $x^{(y^z)}$, not $(x^y)^z=x^{yz}$. $\endgroup$ – David Richerby Dec 21 '14 at 13:58
  • $\begingroup$ Exponential could also mean $2^{O(n)}$. $\endgroup$ – Yuval Filmus Dec 21 '14 at 18:23

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.