Is $ \frac{n^2}{n-2}\in O(n) $ true? Intuitively it seems so but how would I rigorously prove this?
Asymptotic analysis of a ratio
0
$\begingroup$
computer-science
asymptotics
-
0You just need to find $K$ so that for sufficiently large $n$ your function is bounded by $K*n$. It diesn't have to be true immediately for small $n$, and the constant $K$ can be as big as you want for your purpose. – 2012-10-21
3 Answers
3
$ \frac{n^2}{n-2} = n+\frac{2n}{n-2} \leq n+2n= 3n \,,$
since $ \frac{n}{n-2}
-
0The constant 3 cannot be improved on, if the inequality is to hold for all n>2 This is clear since $3^2/(3-2)=9=3*3$. – 2012-10-21
1
Simplify $\frac{n^2}{n-2}$ into $\frac{n^2 - 4}{n-2} + \frac{4}{n-2} = \frac{(n+2)(n-2)}{n-2} + \frac{4}{n-2} = n + 2 + \frac{4}{n-2} \leq n + 6$. Then, as long as $n \geq 6$, $\frac{n^2}{n-2} \leq 2n$, so $\frac{n^2}{n-2} \in O(n)$.
0
By definition (when $\,n\to\infty\,$ in this case, of course)
$\frac{n^2}{n-2}=\mathcal O(n)\Longleftrightarrow\,\exists\,K\in\Bbb R\;\;s.t.\;\; \left|\frac{\frac{n^2}{n-2}}{n}\right|=\left|\frac{n^2}{n^2-2n}\right|\leq K$
when $\,n\to\infty\,$ , and since $\,\displaystyle{\frac{n^2}{n^2-2n}\xrightarrow [n\to\infty]{} 1}\,$ , we're done.