Proving big theta notation?

Question

I need a little guidance solving this problem. I'm trying to show that for every base b > 1;

$(log_b n) = Θ(log _2 n)$

I know that for f(n) to be big-theta it needs to be BigO and BigOmega

So I start off by choosing base b = 2

• And solve BigO first:

BigO Definition: $ (∃K,C>0)(∀n>K) f(n) <= C*g(n)$

So we need to prove that $log_2 n <= ( C ) * ( log _2 n)$ for all n > k

I choose C = 1 and K = 1

$log_2 (n) <= ( 1 ) * ( log _2 n)$ for all n > 1

choose n = 2

$log_2 (2) <= ( 1 ) * ( log _2 2)$ for all n > 1

$log_2 (2) <= ( log _2 2)$ They are equal, so this is true, and will always be true for any n > 1. BigO is proven.

• Solve BigΩ

BigΩ Definition: $ (∃K,C>0)(∀n>K) f(n) >= C*g(n)$

we need to prove that $log_2 n >= ( C ) * ( log _2 n)$ for all n > k

I choose C = 1 and K = 1

$log_2 (n) >= ( 1 ) * ( log _2 n)$ for all n > 1

choose n = 2

$log_2 (2) >= ( 1 ) * ( log _2 2)$ for all n > 1

$log_2 (2) >= ( log _2 2)$ They are equal, so this is true, and will always be true for any n > 1. BigΩ is proven.

Therefore for base b = 2, they equal each other.

Now onto base b = 3.

• Solve BigO first:

We need to prove that $log_3 n <= ( C ) * ( log _2 n)$ for all n > k

choose C = 1, k = 1

$log_3 (n) <= ( 1 ) * ( log _2 n)$ for all n > 1

choose n = 2

$log_3 (2) <= ( log _2 2)$ is true, and will be true for any n > 1

• Solve BigΩ

prove that $log_3 n >= ( C ) * ( log _2 n)$ for all n > k

Can I choose C as a decimal? since if C = 1 , the RHS will always be larger.

I choose K = 1, C = .1

$log_3 (n) >= ( .1 ) * ( log _2 n)$ for all n > 1

choose n = 2

$log_3 (2) >= ( .1 ) * ( log _2 2)$ for all n > 1

$ .630 >= (.1)*(1) $

$ .630 >= (.1) $ TRUE big Omega has been proven

So I guess my question is: Is this method correct? Especially my last Big-Omega, and Is it okay to choose a C = that is a decimal like .1? as long as its > 0

Answer 1

You are making it much too hard.

To show that $(\log_b n) = Θ(\log _2 n) $ you need to show that there are positive $u$ and $v$ such that $u \le \dfrac{\log_b n}{\log _2 n} \le v $.

But $\log_b n = \dfrac{\log_2 n}{\log_2 b} $ so $ \dfrac{\log_b n}{\log _2 n} =\dfrac{\frac{\log_2 n}{\log_2 b}}{\log _2 n} =\dfrac1{\log _2 b} $ and this is all you need.

In fact, the ratio is constant, not just bounded.