Prove whether $2^n = O(n^4 + n^2)$ is true

Question

I have been given a set of questions on BigO for my university course, however I'm really struggling to wrap my head around it, and was wondering if anyone would be able to explain this example please?

The question is:

Decide whether $2^n = O(n^4 + n^2)$ is true, and justify your answer.

We've been given the following information to help us solve the problems, but after following her examples, I'm still struggling to apply it to the tasks. I'd really appreciate any help anyone may be able to give, thanks!

Counting Basic Operations	Time Complexity (bigO)	Name (time)
5	O(1)	constant
n + 3	O(n)	linear
$n^4 + 3n + 1$	O($n^4$)	polynomial
$log(n) + 1$	O($log(n)$)	logarithmic
$log(n) + n^2$	O($n^2$)	polynomial (quadratic)
$nlog(n)$	O($nlog(n)$)	quasilinear
$n^4 + 4^n$	O($2^n$)	exponential
$n! + 2^n$	O($n!$)	factorial

Answer 1

I would recommend using the Limit Comparison test. Take $f(n) = 2^{n}, g(n) = n^{4} + n^{2}$. Now compute: $$L := \lim_{n \to \infty} \frac{2^{n}}{n^{4} + n^{2}}$$.

We have the following:

• If $L = 0$, then $2^{n} \in o(n^{4} + n^{2})$. In particular, $2^{n} \in O(n^{4} + n^{2})$, and $2^{n} \not \in \Omega(n^{4} + n^{2})$.
• If $0 < L < \infty$, then $2^{n} \in \Theta(n^{4} + n^{2})$.
• If $L = \infty$, then $2^{n} \in \omega(n^{4} + n^{2})$. In particular, $2^{n} \in \Omega(n^{4} + n^{2})$ and $2^{n} \not \in O(n^{4} + n^{2})$.

Answer 2

In case you may know that the sequnece $\frac{2^n}{n^4}$ is not bounded then there is a simple trick to determine by contradiction: Suppose that $2^n=O(n^4+n^2)$ then there is $M>0$ and $N>0$ such that for every $n>N$, it is $2^n\leq M(n^4+n^2)\leq M(2n^4)\implies \frac{2^n}{n^4}\leq2M$ , which implies that $\frac{2^n}{n^4}$ is bounded, absurd.

Answer 3

We have $$\displaylines {2^n> {n \choose 5}={n(n-1)(n-2)(n-3)(n-4)\over 5!}\ge {n(n-4)^4\over 120}\\ ={n(2n-8)^4\over 16\cdot 120}\ge {n^5\over 16\cdot 120},\qquad n\ge 8}$$ Hence $${2^n\over n^4+n^2}\ge {2^n\over 2n^4}\ge {n\over 32\cdot 120}, \qquad n\ge 8$$