My question is exactly what the title says. If I have that $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ hold, then does $f(n)=\Theta(g(n))$ hold as well? My intuition says that the second part is false, but I couldn't put this idea on paper.

  • $\begingroup$ Consider the case $f = g$. Can a function be both $\omega(h(n))$ and $o(h(n))$? What can you deduce in the more general case? $\endgroup$ – Yuval Filmus Mar 27 '18 at 19:20
  • $\begingroup$ $f(n) = n\log n, g(n) = \log n, h(n)=n$ $\endgroup$ – Mickey Mar 27 '18 at 19:23
  • $\begingroup$ Do you mean $\omega$ or $\Omega$? $\endgroup$ – Raphael Mar 28 '18 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.