0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You’re doing great so far, but here’s the MathJax tutorial. You can reference it for tips on further beautifying your post. $\endgroup$ – Chase Ryan Taylor Jan 15 '18 at 4:30
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you, I think I'm getting it. For any question trying to prove f(n) = Θ(g(n)) , can you say that you need to show it as u <= [ f(n) / g(n) ] <= v where u and v are positive? When you simplify log2(n) / log2(b) into 1/log2(b), how does that prove that our original f(n) = theta( g(n) )? Are you showing that log2(n) / log2(b) can be simplified so that there is no n value ? and that would prove it to be big-theta $\endgroup$ – Martin Jan 15 '18 at 3:51
  • $\begingroup$ 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$. $\endgroup$ – marty cohen Jan 15 '18 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.