# Proving big theta notation?

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

• You’re doing great so far, but here’s the MathJax tutorial. You can reference it for tips on further beautifying your post. – gen-ℤ ready to perish Jan 15 '18 at 4:30

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.
• Right. The cases are: $f(n) =O(g(n))$ means $f(n)/g(n)$ is bounded above;$f(n) =\Omega(g(n))$ means $f(n)/g(n)$ is bounded below;$f(n) =\Theta(g(n))$ means $f(n)/g(n)$ is bounded both above and below;$f(n) =o(g(n))$ means $f(n)/g(n) \to 0$. – marty cohen Jan 15 '18 at 3:56