0
$\begingroup$

Is $ \frac{n^2}{n-2}\in O(n) $ true? Intuitively it seems so but how would I rigorously prove this?

  • 0
    You 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

3

$ \frac{n^2}{n-2} = n+\frac{2n}{n-2} \leq n+2n= 3n \,,$

since $ \frac{n}{n-2} 2 $

  • 0
    The 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.