1

I should end up with a range for $a$, but I end up with a single value for $a$ after evaluating $Big$ $O$ and $Big$ $\Omega$.

Problem: Prove $\log_a(n)$ is $Big$ $\Theta$ $(\log_2(n))$. For which range of values of a is this true?

UPDATE: My work so far...

For $Big$ $O$:

$\log_a(n) \leq c * \log_2(n)$

$\frac{\log_2(n)}{\log_2(a)} \leq c * \log_2(n)$

$2^\frac{1}{c} \leq a$

For $Big$ $\Omega$:

$2^\frac{1}{c} \geq a$

Stone
  • 13
  • 1
    I tried to edit your post but suddenly I realized I can't: I just don't understand it.Please do type with LaTeX as supported in this forum. – DonAntonio Sep 19 '12 at 11:17
  • I modified the post to fit LaTeX syntax. Please let me know if it still isn't clear. – Stone Sep 19 '12 at 11:29
  • 1
    You know that $\log_a n = \frac{\log_2 n}{\log_2 a}$? – martini Sep 19 '12 at 11:31
  • Right, I just updated the post with my work. I'm sure I have to do a log base conversion, but I'm not sure where to go from there. I think I'm lacking some conceptual understanding of how to approach the problem... – Stone Sep 19 '12 at 11:40

1 Answers1

1

Do you mean you want to prove

$$\log_an=\mathcal O(\log_2 n)\,\,?$$

If so, then

$$\log_an=\frac{\log_2n}{\log_2a}=\mathcal O (\log_2 n)\Longleftrightarrow \frac{1}{\log_2a}\,\,\,\text{is bounded}$$

Well, $\,\log_2a\,$ is a constant , so...(of course, the basic assumption is $\,1<a\neq 1\,$)

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • OH! That makes sense. Thanks! And $a$ can't be a decimal because in order for $Big$ $\Omega$ to be true, $a$ needs to be positive which would require placing an upper bound on $n$? – Stone Sep 19 '12 at 12:13