1

In one of my exercise sheets I have the following question;

Let $f,g: \mathbb{N}\longrightarrow\mathbb{R}$ be positive functions with $f(n) \in O(g(n))$. Prove or disprove; $\ln(f(n)) \in O(\ln(g(n))$.

I first thought this would be the case since ln is a monotonically increasing function ( derivative is positive ) the asymptotic ordering of these functions wouldn't be affected. But then there was an example stuck in my mind and which I have later on seen on the internet as well.

Let $f(n) = 2^n,g(n)=3^n$. Since $f(n) \in O(g(n))$ given $\lim_{n\to \infty} \frac{3^n}{2^n}=\infty$. Then $\ln(f(n))=n*\ln 2$ and $\ln(g(n))=n*\ln 3$ which leads to $ 0< \lim_{n\to \infty} \frac{n*\ln 3}{n*\ln 2} < \infty$ which implies $\ln (f(n)) \in \Theta(\ln(g(n)))$. The growth rates have changed yes but since $\Theta(f) = O(f) \cap\Omega(f)$ isn't, technically speaking, $\ln(f(n)) \in O(ln(g(n)))$ ? I am a bit confused as going by my own steps the initial assumption seems right but I am not entirely convinced for either possibility. Because if this is correct I feel like I can extend the same idea for exponentiation as well maybe.

Anything to prove or disprove the statement with an explanation would be really welcome as I am a bit lost at the moment.

Bernard
  • 175,478
Yiğit Aras Tunalı
  • 115

1 Answers1

0

In this answer, I'll denote by $\log$ the natural logarithm, which is equivalent to the $\ln$ notation you use (this is just a personal preference).

The claim is not true in general. Define $f,g:\mathbb{N} \to \mathbb{R}$ by $f(n) = 1 + 1/n$ and $g(n) = 1 + e^{-n}$. We can first note that each of the four functions $f(n), g(n), \log f(n), \log g(n)$ are positive for all natural $n$. We also note that $f(n) \in O(g(n))$, since $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$. On the other hand, since $\log f(n) = \log(1 + 1/n) \sim 1/n$ and $\log g(n) = \log(1 + e^{-n}) \sim e^{-n}$ as $n \to \infty$, we have that $$\lim_{n \to \infty} \frac{\log f(n)}{\log g(n)} = \lim_{n \to \infty} \frac{1/n}{e^{-n}} =\lim_{n \to \infty} \frac{e^n}{n} = \infty $$ so that $\log f(n) \notin O(\log g(n))$.

The claim does hold if $\alpha = \liminf_{n \to \infty} g(n) > 1$ and $f(n) \geq 1$ for all but finitely many $n$. In this case, if $f(n) \in O(g(n))$ then for some constant $C>0$, we have that $f(n) \leq Cg(n)$ for large $n$. Hence $$\limsup_{n \to \infty} \frac{\log f(n)}{\log g(n)} \leq \limsup_{n \to \infty} \frac{\log Cg(n)}{\log g(n)} = \limsup_{n \to \infty} \frac{\log C + \log g(n)}{\log g(n)} = 1 + \limsup_{n \to \infty} \left(\frac{\log C}{\log g(n)}\right)$$ $$\leq 1 + \frac{\log C}{\log \alpha} < \infty$$

so that $\log f(n) \in O(\log g(n))$.

In particular, this means that if $f(n), g(n) \xrightarrow[n \to \infty]{} + \infty$, then indeed the implication $f \in O(g) \rightarrow \log f \in O(\log g)$ holds, and this is most likely what we will encounter in practice (e.g., in computer science when analyzing algorithms, say).

MathematicsStudent1122
  • 12,462
  • If you wouldn't mind me asking, could you explain why $log(1+1/n)$ ~ $1/n$ ? As for the limit inf and limit sup arguments, I'll need to look more into it as I am not entirely sure if I know the concept. But thanks for your answer! – Yiğit Aras Tunalı Oct 27 '19 at 10:43
  • Also, the example you gave is $f(n) \in \Theta(g(n))$ at first. I know theta implies big-oh as well but the question states $f(n) \in O(g(n))$ so I just want to make sure we are abiding by the limitations of the question. ( for the $f(n)= 1+1/n$ example you gave at the beginning of your question) – Yiğit Aras Tunalı Oct 27 '19 at 11:51
  • @YiğitArasTunalı To answer your first question: it's because $$\lim_{x \to 0} \frac{\log(1+x)}{x} = 1$$, and this limit can be proved since it's simply the derivative $g'(0)$ where $g(x) = \log(1+x)$. – MathematicsStudent1122 Oct 27 '19 at 21:51
  • @YiğitArasTunalı To answer your second question, $f \in \Theta(g)$ implies $f \in O(g)$. You seem to recognize this. There's not much else to add. – MathematicsStudent1122 Oct 27 '19 at 21:51
  • Quick update apparently it is not correct; with the counter-example: $f(n) = e$ and $g(n) = e^{1/n}$. – Yiğit Aras Tunalı Nov 02 '19 at 23:13
  • @YiğitArasTunalı Yea, that works too. – MathematicsStudent1122 Nov 02 '19 at 23:15