Using the definition of Θ prove or disprove the following:

Question

$$ \dfrac{4n^4 -18n^3 +3n^2 -660}{n^2 +560n -1024} = Θ(n^2) $$

It's been quite a while since I've one this as a ratio and I'm a bit lost on what steps to take for this. I know we'll need to prove both big O and big Omega but simplifying the ratio has me stuck.

Answer 1

HINT: Divide it out to get

$$f(n)=\frac{4n^4-18n^3+3n^2-660}{n^2+560n-1024}=4n^2+an+b+\frac{cn+d}{n^2+560n-1024}$$

for some $a,b,c,d\in\Bbb R$. Show that

$$\left\vert an+b+\frac{cn+d}{n^2+560n-1024}\right\vert\le n^2$$

for sufficiently large $n$ and conclude that $n^2\le f(n)$ and $f(n)\le 5n^2$ for sufficiently large $n$.

Answer 2

This ratio can be rewritten as $f(n)=n^2g(1/n)/h(1/n)$ where $g(x)=4-18x+3x^2-660x^3$ and $h(x)=1+560x-1024x^2$. Hence $g(x)\to4$ and $h(x)\to1$ when $x\to0$, which implies that $g(1/n)/h(1/n)\to4$ when $n\to\infty$. Pick some $N$ such that $|g(1/n)/h(1/n)-4|\leqslant1$ for every $n\geqslant N$, then $3n^2\leqslant f(n)\leqslant5n^2$ for every $n\geqslant N$, in particular $f(n)=\Theta(n^2)$.

Quantitatively: If $|x|\leqslant\frac1{10,000}$, $3\leqslant g(x)\leqslant5$ and $\frac12\leqslant h(x)\leqslant\frac32$ hence, for every $n\geqslant10,000$, $2n^2\leqslant f(n)\leqslant10n^2$.