Is lg x=O(ln x) ?
Is ln x=O(lg x)?

here lg means  log with base 2
     ln means  log with base e
and O is big oh notation

Hi seurhe!!

Let me start with a definition:
Let n be the size of the input and f (n), g(n) be positive functions
of n:
f(n) = O(g(n)) is equivalent to say "There exist positive constants x
and k such that for all n>k, f(n) =< x*g(n)"

One of the properties of the logarithms is:

log-a(n) = log-b(n) / log-b(a) 

Here log-a(n) means logarithm with base a of n.

Then we have:
lg(n) = ln(n)/ln(2) = (1/ln(2)).ln(n) = c1.ln(n);
then lg(n) is O(ln(n))

Also
ln(n) = lg(n)/lg(e) = (1/lg(e)).lg(n) = c2.lg(n);
then ln(n) is O(lg(n)).

In cases like that we say that lg(n) is big-theta of ln(n). For
reference about that visit the following page from Everything2.com:
"Big-oh notation":
http://www.everything2.com/index.pl?node=Big-oh%20notation

I hope this helps you. Please,if you find this answer unclear, request
an answer clarification  before rate this answer.

Best regards.
livioflores-ga

---

Request for Answer Clarification by seurhe-ga on 03 Sep 2003 11:04 PDT

Hi Livioflore,

So the answer is yes for both notation? Both the notation satisfies
Big Oh vicevarsa. Please reply me.

---

Clarification of Answer by livioflores-ga on 03 Sep 2003 11:16 PDT

Hi seurhe!!

Yes, the answer is yes for both notation; this is because they are
related by constant ratios.

Regards.
livioflores-ga