Proving Big-Omega

2,320

$\dfrac{n^2}2$ remains below $n^2-3$ as of $n=3$. Then you have it.

Share:
2,320

Related videos on Youtube

Faisal148991
Author by

Faisal148991

Updated on October 26, 2020

Comments

  • Faisal148991
    Faisal148991 about 3 years

    I have a tutorial sheet that asks:

    Prove that $n^2 - 3$ is $\Omega(n^2)$

    I understand that:

    $$f(n) ≥ c g(n) $$

    And that to $c > 0$ & $n > n_{0}$

    The problem is that what ever $C$ value I use I keep ending up where the $n^2$ value shall fall into the negative domain.

    Any help would be greatly appreciated

    • RideTheWavelet
      RideTheWavelet about 6 years
      I'm not entirely sure what you mean. For all $n\geq 2,$ $$\frac{n^{2}-3}{n^{2}}\geq \frac{1}{4},$$ right?
    • Faisal148991
      Faisal148991 about 6 years
      @RideTheWavelet we have to use the definition, f(n) ≥ c g(n) to prove that n² - 3 is Ω(n²), so I need to find either a trivial case of C or use some other form of proof. Does that help clarify?
    • RideTheWavelet
      RideTheWavelet about 6 years
      Doesn't what I've written do exactly that?
    • Faisal148991
      Faisal148991 about 6 years
      @RideTheWavelet how did you know what c value to pick?
    • RideTheWavelet
      RideTheWavelet about 6 years
      Well for this example, I saw that when $n=1,$ I got $-2$ as the value, but once I picked $n=2,$ I got something positive. Since the left hand side is increasing in $n,$ $1/4$ works. We could just as well have chosen $n_{0}=3$ and $c=2/3.$
    • Faisal148991
      Faisal148991 about 6 years
      Ah I see, thank you for the help and explanation!