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$
1
  • $\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$ Jan 15, 2018 at 4:30

1 Answer 1

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$
2
  • 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, 2018 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$ Jan 15, 2018 at 3:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .