Why is this the case? I understand that if $f(n) = \Theta (g(n))$ then $c_1g(n)
If $f(n) = \Theta (g(n))$, why does $g(n) = \Omega (f(n))$?
0
$\begingroup$
discrete-mathematics
asymptotics
intuition
-
0In this question, you provide no background, and your question is unclear about how precisely you use $\Theta$ and how you use $\Omega$ and how you choose $c_{1}$ and $c_{2}$. This question, as is, is unhelpful. – 2012-12-17
-
1If $f$ is $O(g)$, then $g$ is $\Omega(f)$. – 2012-12-17
-
0@Jebruho: The wording is a little sloppy in places, but the question is perfectly understandable. – 2012-12-17
-
0@Jebruho The exact question is: True or false: $[f(n) = \Theta (g(n))] \rightarrow [g(n) = \Omega (f(n))]$. The answer is apparently true, but I don't understand why. – 2012-12-17
1 Answers
1
If $f(n)$ is $\Theta\big(g(n)\big)$, then $f(n)$ is $O\big(g(n)\big)$, and there are a positive constant $c$ and an $n_0\in\Bbb N$ such that $|f(n)|\le c|g(n)|$ for all $n\ge n_0$. But then $|g(n)|\ge\frac1c|f(n)|$ for all $n\ge n_0$, and $\frac1c>0$, so $g(n)$ is $\Omega\big(f(n)\big)$.
-
0So what's the difference between $\Theta$ and $O$ if they both bound the function above? – 2012-12-17
-
0@BailorTow: $f$ is $\Theta(g)$ if and only if $f$ is both $O(g)$ **and** $\Omega(g)$. – 2012-12-17
-
0Oh, OK. So then $g$ is also $O(f)$? – 2012-12-17
-
0@BailorTow: Yes: loosely speaking the two functions have the same order of magnitude. – 2012-12-17