Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|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
up vote 3 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|cite|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

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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.