patternMinor
Is Big-Oh notation preserved under monotonic functions?
Viewed 0 times
monotonicpreservedbigundernotationfunctions
Problem
I was just looking at the big-Oh notation. I wanted to know if the following is true in general
$$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$
I can prove that this is true if $g$ is monotonically increasing, but am not sure if this holds in general.
$$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$
I can prove that this is true if $g$ is monotonically increasing, but am not sure if this holds in general.
Solution
By definition,
$$ f(n) \in O(g(n))$$
means there exists some positive constant $c$, such that for any large enough $n$,
$$ |f(n)| \le c |g(n)|$$
or equivalently, $\lim_{n\to\infty} \frac{f(n)}{g(n)} \le c (actually, the above example of $2^{-n}$ vs $1/n$ satisfies $g(n)\to 0$ rather than $log(g(n))\to 0$. Oops).
If we take $f(n) = 2 + 1/n$ then $\log f(n) \to 1$ (binary log, obviously).
so while $f(n) \le 3g(n)$ for every $n\ge 1$, it is not true that
$\log f(n) \le c' \log g(n)$ for all large enough $n$, as the right-hand side approaches zero, while the left-hand side approaches 1.
$$ f(n) \in O(g(n))$$
means there exists some positive constant $c$, such that for any large enough $n$,
$$ |f(n)| \le c |g(n)|$$
or equivalently, $\lim_{n\to\infty} \frac{f(n)}{g(n)} \le c (actually, the above example of $2^{-n}$ vs $1/n$ satisfies $g(n)\to 0$ rather than $log(g(n))\to 0$. Oops).
If we take $f(n) = 2 + 1/n$ then $\log f(n) \to 1$ (binary log, obviously).
so while $f(n) \le 3g(n)$ for every $n\ge 1$, it is not true that
$\log f(n) \le c' \log g(n)$ for all large enough $n$, as the right-hand side approaches zero, while the left-hand side approaches 1.
Context
StackExchange Computer Science Q#28068, answer score: 5
Revisions (0)
No revisions yet.