How can I show that $n^2 - 2n - 3$ is $\Omega(n^2)$?
Asked
Active
Viewed 195 times
0
-
What is $\Omega(n^2)$? – awllower Jul 06 '13 at 01:32
-
why the downvote? – Sidharth Ghoshal Jul 06 '13 at 01:44
-
Did you down-vote my question? If $f(x)$ is $\Omega(n^2)$ it means that $f(x) \ge \Omega(n^2)$ for some values $C$ and $k$ such that $x \ge k$ and $C$ is a constant multiple of $n^2$. – Jul 06 '13 at 01:44
-
I did not downvote; I was just curious about the definition of that symbol. I thought of it as big $O$. Clearly this is not the case, though. Also, what does $f(x)\ge \Omega(n^2)$ mean? You define $\Omega(n^2)$ by means of itself? – awllower Jul 06 '13 at 01:47
-
Oh, no problemo. Yeah, I barely understand Big-O. Big-Omega is apparently the opposite. $\ge$ intsead of $\le$. – Jul 06 '13 at 01:50
-
A related problem. – Mhenni Benghorbal Jul 06 '13 at 02:01
1 Answers
2
Since $2n+3$ is positive for any choice of $n$, $$n^2-2n-3\leq n^2$$ for any $n\geq 1$.
Now, $$-\frac 1 3 n^2\leq -3$$ and $$-\frac 1 3 n^2\leq -2n$$ when $n\geq 5$. Thus $$n^2-\frac 23n^2=\frac 13n^2\leq n^2-2n-3$$ when $n\geq 5$. We can then write $$\frac 13n^2\leq n^2-2n-3\leq n^2$$ for $n\geq 5$
Pedro
- 122,002
-
-
-
-
-
So I took a break and came back to this problem. I came up with $C = -1$ and $k \ge 2$. Would those be appropriate witnesses to say that $n^2 - 2n - 3$ is $\Omega (n^2)$? – Jul 06 '13 at 03:40
-
Update: My logic is: $n^2 \le n^2$ when $n>=1$ and $C=1$, $n^2 \le -2n$ when $n>=2$, and $C=-1$ and $n^2 \le -3$ when $n>=2$ and $C =-1$. Summing the coefficients results in $-1$ and the $max(k_1,k_2,k_3) = 2$. – Jul 06 '13 at 03:42