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.

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|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 en.wikipedia.org/wiki/Big_O_notation –  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 1

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|improve this answer
    
its from a slide presentation given to us from our instructor. –  JR Galia Dec 13 '11 at 17:14
5  
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

 
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.