Big Omega Notation

Question

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

score 1 · Accepted Answer · answered Dec 13 '11 at 16:58

1

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

answered Dec 13 '11 at 16:58

joriki

its from a slide presentation given to us from our instructor. – JR Galia Dec 13 '11 at 17:14
6

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
If $n\gt10$, then $n\geqslant11$ hence $19n/20\geqslant10.45\gt10$ hence $n\gt10+(n/20)$ hence $n-10\gt n/20$. – Did Dec 14 '11 at 07:24
@joriki, +1 for the choice comment. – Did Dec 14 '11 at 07:27

1 Answers1