Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  coffeemath Oct 21 '12 at 6:24
add comment

3 Answers

up vote 2 down vote accepted

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

since $ \frac{n}{n-2}<n\,, \forall n > 2 $

share|improve this answer
    
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$. –  coffeemath Oct 21 '12 at 7:09
add comment

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)$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.