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
-
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)$.
-
0@BailorTow: Yes: loosely speaking the two functions have the same order of magnitude. – 2012-12-17