Example of function f(x) such that it is true that f(x) = Ω(g(x)) but that it is not true that f(x) = ω(g(x))
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Pick $f(x) = g(x) = x$. Then $f(x) \in \Omega(g(x))$ and $f(x) \not \in \omega(g(x))$.
-
$\begingroup$ I think this is quite a good example! Just to emphasize, Ω is the upper bound, while 𝜔 is the tight upper bound. $\endgroup$ Commented Feb 25, 2023 at 9:41
-
$\begingroup$ @shripalmehta: sorry, but you are wrong is several ways. An $\Omega$ bound may be tight, while an $\omega$ bound is not. Both are lower bounds. $\endgroup$– user16034Commented Mar 27, 2023 at 7:42
$\begingroup$
$\endgroup$
1
f(x) = Ω(g(x)) , f(x) = ω(g(x))
Ω(g(x)) = ω(g(x))
0 = (ω - Ω)(g(x))
We have a TRUE statement whenever the difference between small omega and big omega approaches zero.
Define indicator function: when big omega, then TRUE, else (small omega) -> FALSE.
-
$\begingroup$ Ω(x) is the upper bound, while ω(x) is the tight upper bound (i.e. the function yields a value near to, but never equal to the upper boundary). These are 2 different things, you started off stating that they are the same. Hence, everything went down the wrong path. $\endgroup$ Commented Feb 26, 2023 at 18:19