0

I'm struggling to show that : $n^{n-2} = O(2^{n^2})$ .

I know the definition of big O but I don't know any method to show this. Could you please help me giving a few methods?

Marine Galantin
  • 2,956
  • 1
  • 16
  • 33
  • 3
    $n^{n-2} = o(n^n)$, and $n^n \leq (2^n)^n=2^{n^2}$. – Aphelli Jan 21 '19 at 13:24
  • 2
    The takeaway from this is that exponents matter much more than bases. The same approach shows $n^n=o(2^{n^2})$. Even though the base of $n^n$ is rising it can't compete with the larger exponent. – Ross Millikan Jan 21 '19 at 18:30

2 Answers2

4

$$\lim_{n\to\infty}\frac{n^{n-2}}{2^{n^2}}=\lim_{n\to\infty}\frac1{n^2}\cdot\Big(\frac{n}{2^n}\Big)^n=0$$

Shubham Johri
  • 17,659
4

Here is a less obvious approach for the cases when it will not be as simple as in Shubham's answer. Note that $f(x) < g(x) \iff \ln f(x) < \ln g(x)$ and compare the logs to get $$ \ln\left(n^{n-2}\right) = (n-2) \ln n = \Theta(n \ln n) $$ versus $$ \ln \left(2^{n^2}\right) = n^2 \ln 2 = \Theta\left(n^2\right)... $$

gt6989b
  • 54,422