2

How can someone calculate the asymptotic upperbound of $2^nn^2$? The first term ($2^n$) grows much faster than the second, but saying that as a final result $2^nn^2 = O(2^n)$ would only be true in the case we had in addition, right? How does it work in multiplication?

bibliobibuli
  • 23

2 Answers2

1

We could say that for any positive $\epsilon$, we have $n^22^n=O(2^{n+\epsilon})$. That is occasionally useful.

You are right in saying that it is not $O(2^n)$.

André Nicolas
  • 507,029
  • with no need to specify $\epsilon$? And what happens in the occasion that instead of $2^n$, we have a term that is growing even faster, such as $n!$? Could we say, then, that $n^2n! = O(n!)$? – bibliobibuli Apr 30 '16 at 17:57
  • Any positive $\epsilon$ makes the big O statement true. For your second question, it is not true that $n^2n!=O(n!)$, since there is no constant $K$ such that after a while $n^2n!\le Kn!$. – André Nicolas Apr 30 '16 at 18:01
  • Then what would be the asymptotic of upperbound $n^2n!$ ? – bibliobibuli Apr 30 '16 at 22:22
  • Well, we can always use $n^2n!$. Or if you prefer, we could say it is $O((n+2)!)$. We can use the Stirling approximation to $(n+2)!$ to give a potentially somewhat more useful form. Or we can use the Stirling approximation to $n!$, and multiply by $n^2$. – André Nicolas Apr 30 '16 at 22:26
0

It holds that $2^n n^2= O(2^n n^2)=O(2^n n^3)= \dots=O(2^n 2^m)=O(2^{n+m})$

Evinda
  • 1,460