0
$\begingroup$

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

  • 0
    whats this big omega notation used for? i googled the tag of the ques, but couldnt get the answer.. any help pelase?2011-12-13
  • 0
    @168335 http://en.wikipedia.org/wiki/Big_O_notation2011-12-13
  • 0
    It is used in computational complexity. http://blog.computationalcomplexity.org/2005/01/big-omega.html2011-12-13

1 Answers 1

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.

  • 0
    its from a slide presentation given to us from our instructor.2011-12-13
  • 5
    Then I guess you'll have to choose between your instructor and arithmetic. I'd choose arithmetic.2011-12-13
  • 0
    i chose arithmetic... but I will listen to an explanation 9 hours from now.2011-12-13
  • 0
    I suspect the explanation might be that $n\ge10$ was supposed to be $n\gt10$ (with $n$ integer).2011-12-13
  • 0
    how is n>10 used to come up n – 10 ≥ n / (2 x 10)?2011-12-13
  • 0
    If $n\gt10$, then $n\geqslant11$ hence $19n/20\geqslant10.45\gt10$ hence $n\gt10+(n/20)$ hence $n-10\gt n/20$.2011-12-14
  • 0
    @joriki, +1 for the *choice* comment.2011-12-14