1
$\begingroup$

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$

  • 0
    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...2012-09-19

1 Answers 1

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)

  • 0
    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$?2012-09-19