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
    It is used in co$m$putational 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
    @joriki, +1 for the *choice* comment.2011-12-14