If $f(x)$ and $g(x)$ are two functions such that
$$f(x) \not\in \Omega(g(x))$$
does
$$\log f(x) \not\in \Omega(\log g(x))$$
hold?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
This does not hold for all $f$, $g$. Consider $f(x) = x!$ and $g(x) = x^x$. It is the case that $x! \not\in \Omega(x^x)$ yet, using Stirling's approximation, we have that
$$\log (x!) \in \Theta(x \log x)$$
Since, $\log(x^x) = x \log x$, we have
$$\log f(x) \in \Theta(\log g(x))$$
-
$\begingroup$ An even simpler example would be $f(x)=x$ and $g(x)=x^2$. $\endgroup$– Discrete lizard ♦Commented Jan 19, 2018 at 8:20
-
$\begingroup$ @Discretelizard Yeah. Thats a way better example. I was over thinking this one. $\endgroup$ Commented Jan 19, 2018 at 8:21