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$
$\endgroup$
3
-
$\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 FilmusCommented Mar 27, 2018 at 19:20
-
$\begingroup$ $f(n) = n\log n, g(n) = \log n, h(n)=n$ $\endgroup$– MickeyCommented Mar 27, 2018 at 19:23
-
$\begingroup$ Do you mean $\omega$ or $\Omega$? $\endgroup$– RaphaelCommented Mar 28, 2018 at 10:02
Add a comment
|