Proving Big-Omega
2,320
$\dfrac{n^2}2$ remains below $n^2-3$ as of $n=3$. Then you have it.
Related videos on Youtube
Author by
Faisal148991
Updated on October 26, 2020Comments
-
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 about 6 yearsI'm not entirely sure what you mean. For all $n\geq 2,$ $$\frac{n^{2}-3}{n^{2}}\geq \frac{1}{4},$$ right?
-
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 about 6 yearsDoesn't what I've written do exactly that?
-
Faisal148991 about 6 years@RideTheWavelet how did you know what c value to pick?
-
RideTheWavelet about 6 yearsWell 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 about 6 yearsAh I see, thank you for the help and explanation!
-