# Big Omega Notation

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

-
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
–  Casey Robinson Dec 13 '11 at 17:55
It is used in computational complexity. blog.computationalcomplexity.org/2005/01/big-omega.html –  JR Galia Dec 13 '11 at 17:57

## 1 Answer

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

-
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