Applying log on both sides to decide whether $f(n)=O(g(n))$ or $g(n) = O(f(n))$? If i have to decide which function is bigger, can i apply logarithm on both sides and infer?
For example, $n $ vs $\sqrt n$
[On face of it i know that n>$\sqrt n$]
If i apply log function
$\ln n $ vs $\frac{1}{2} \ln n$
Both are asymtotically equal(differing by constant?) But it is not true right?
[To decide whether (In algorithm Big oh notation, )$f(x) = O(g(x))$]
My doubt is
If i had to decide whether $f(n)=O(g(n))$ or $g(n) = O(f(n))$, i apply log on both sides. Some times it does not give right answer(for instance above one). Can you pls tell when will applying log on both sides go wrong?
I am a beginner. kindly clarify.
 A: As I wrote above $\sqrt{n} \lt n$ implies $\ln\sqrt{n} = \frac{1}{2}\ln n \lt \ln n$.
This fact does not interfere with the fact that  $O(\ln n) = O\left( \frac{1}{2}\ln n \right)$. It's possible, that $f(n) \lt g(n)$, but $O(f)=O(g)$, as it gives brought example. We have  $O(\sqrt{n} )\subset O(n)$ strictly.
On another hand, words "asymptotically equal", "same order of magnitude" usually, is used for big-$\Theta$ notation, not for big-$O$. Used this notation we can say, again, that despite that $\sqrt{n}$ and $n$ are not asymptotically equal, i.e. $\Theta(\sqrt{n})\ne \Theta(n)$,  the for pair $\ln\sqrt{n}$ and $\ln n$ holds $\Theta(\ln\sqrt{n})=\Theta(\ln n)$.
So, we can formulate little rule: increasing function doesn't keep "asymptotically not equality".
Addition.
Let me first present the answer in the form of an affirmative and then a negative sentence. Suppose we generalize the notion of positive functions asymptotically equivalent to the notion of having the same order, i.e., when there is a limit $\lim\frac{f}{g}=L\gt 0$. If all conditions of Lopital's rule are satisfied for given functions, then, assuming that all expressions written out make sense, we have $\lim\frac{\ln f}{\ln g} = \lim\frac{ \frac{ 1}{ f}f'}{\frac{ 1}{ g}g'} = 1$. So, we can say, that in described conditions, if $f,g$ have same order, then $\ln f,\ln g$ also will have same order. As negative sentence we can formulate it in following way: if $\ln f,\ln g$ have not same order, then $f, g$ also will not have same order.
A: The definition of $f(x) = O(g(n))$ is that exists $C$ such that $|f(n)| \le C |g(n)|$ for $n$ big enough.
Applying $\log$ preserves inequalities, BUT transforms products into sums. Since the definition of $f(n) = O(g(n))$ involves a product, $f(n) = O(g(n))$ is NOT equivalent to $\log f(n) = O(\log g(n))$.
For example, take $f(n)=n^2$ and $g(n) = n$, then $\log f(n) = O(\log g(n))$ but $f(n) \ne O(g(n))$.
On the other hand, take $f(n) = 1/n$ and $g(n)=1$. Then $f(n)=O(g(n))$ but $\log f(n) \ne O(\log g(n))$.
So neither of the implications
$f(n) = O(g(n)) \implies \log f(n) = O(\log g(n))$
$\log f(n) = O(\log g(n)) \implies f(n) = O(g(n))$
is true.
