Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
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
add comment

1 Answer

up vote 1 down vote accepted

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\,$)

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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