Show that $f(n) = 2n^4 + 4n^2 + 5$ has a tight bound of $\Theta(n^4)$

722 Views Asked by At

What I have done so far (planning on showing lower and upper bound first):

Lower bound:

$$c_1n^4 \leq 2n^4 + 4n^2 + 5$$ Divide by $n^4$

$$c_1 \leq 2 + \frac{4}{n^2} + \frac{5}{n^4}$$

Take limit as n approaches infinity

$$c_1 \leq 2 + 0 + 0$$

Therefore

$c_1 \leq 2$ and $n \geq 1$

I am not sure how to show the upper bound. How do I find a $c_2$ that is greater than $f(n)$?

Thanks.

Note: The question requires that I show the upper and lower bounds

1

There are 1 best solutions below

1
On BEST ANSWER

You can just use the limit definition of the Theta notation.

$$\lim_{x\to\infty} \frac{f(n)}{g(n)} = v$$

where in this case $f(n)$ is $2n^4+4n^2+5$ and $g(n) =n^4$. And we know that if $0<v<\infty$ then $f(n)\in \Theta(g(n))$. So,

$$\lim_{x\to\infty} \frac{f(n)}{g(n)}= \lim_{x\to\infty} \frac{2n^4+4n^2+5}{n^4}=\lim_{x\to\infty}\left( 2+\frac{4}{n^2}+\frac{5}{n^4}\right) = 2$$

So therefore, $f(n)\in \Theta(n^4)$

$\textbf{Alternatively,}$

An upper bound can be obtained by noting that

$$2n^4+4n^2+5 \leq 2n^4+4n^4+5= 6n^4+5 $$

So $6n^4+5$ can be your upper bound. Now for the lower bound,

$$2n^4+4n^2+5\geq 2n^4 +4 +5 = 2n^4+9$$

and you may choose $2n^4+9$ as your upper bound.