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

Using basic definition, we show that $n^2 - 10n = \Omega(n^2)$.

For, $n \geq \frac{n}{2}$ for $n \geq 0$

$n – 10 \geq \frac{n}{2 \cdot 10}$ for $n \geq 10$

$n^2 - 10n \geq \frac{n^2 }{ 20}$ for $n \geq 10$

$ n^2 - 10n \geq c \cdot n^2$ for $n \geq n_0$ where $c= \frac{1}{20}$ and $n_0 = 10$.

Therefore, by basic definition, $n^2 - 10n = \Omega(n^2)$.

I don't understand how this inequality was derived: $n – 10 \geq \frac{n }{2 \cdot 10}$.

share|cite|improve this question
whats this big omega notation used for? i googled the tag of the ques, but couldnt get the answer.. any help pelase? – Bhargav Dec 13 '11 at 17:51
@168335 – Casey Robinson Dec 13 '11 at 17:55
It is used in computational complexity. – JR Galia Dec 13 '11 at 17:57
up vote 1 down vote accepted

That's because it's wrong. Substituting $10$ yields $10-10=0$ on the left but $10/(2\cdot10)=1/2$ on the right.

share|cite|improve this answer
its from a slide presentation given to us from our instructor. – JR Galia Dec 13 '11 at 17:14
Then I guess you'll have to choose between your instructor and arithmetic. I'd choose arithmetic. – joriki Dec 13 '11 at 17:16
i chose arithmetic... but I will listen to an explanation 9 hours from now. – JR Galia Dec 13 '11 at 17:53
I suspect the explanation might be that $n\ge10$ was supposed to be $n\gt10$ (with $n$ integer). – joriki Dec 13 '11 at 18:17
how is n>10 used to come up n – 10 ≥ n / (2 x 10)? – JR Galia Dec 13 '11 at 23:06

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.