1
$\begingroup$

Figuring out the lowest Big-O for $\ 7n^2$ for example, is straight-forward by finding witnesses C and k such as $\ n > 7 $ therefore $\ 7n^2 < n^3 $ so k = 7 and C = 1. So $\ 7n^2 $ has Big-O($\ n^3$)

But, how do I find the lowest Big-O for something like $\ 3^{n^3}$?

  • 0
    Yes, it is indeed. It's also included in n^3 subset. It was a bad example considering my question of having the lowest Big-O possible. Sorry.2012-10-07

1 Answers 1

1

I don't see much that you can do with $3^{n^3}$. However, you can write it as $e^{\ln(3) n^3}$, and this could be written as $e^{O(n^3)}$. It could also be written as $e^{n^{O(1)}}$, but this almost seems an abuse of big-O notation, since so much information is lost at each step.