Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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
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|cite|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

Your Answer


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.