0
$\begingroup$

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 ?

$\endgroup$
1
  • 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
    Commented Dec 21, 2014 at 11:14

1 Answer 1

5
$\begingroup$

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

$\endgroup$
4
  • $\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
    Commented Dec 21, 2014 at 11:33
  • 1
    $\begingroup$ $3^{(1/3)^n} \neq 3^{n/3}$. $\endgroup$ Commented Dec 21, 2014 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$ Commented Dec 21, 2014 at 13:58
  • $\begingroup$ Exponential could also mean $2^{O(n)}$. $\endgroup$ Commented Dec 21, 2014 at 18:23

Your Answer

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

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