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))


2 Answers 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$
    – user16034
    Commented Mar 27, 2023 at 7:42
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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.