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.

Hi I need help figuring these out:

True or False: $\log_2 n$ is $O(\log_3 n)$

I used the definition of Big O in Dasgupta's book: ${f(n)}\over g{(n)}$ $\leq c$

So I used the base transformation rule to get: ${(\log_2 3)(\log_3 n)}\over \log_3 n$ $\leq c$

Which just gives me $\log_2 3 \leq c$

So I got false as the answer, what I'm not sure about is if I did this correctly and if it makes sense in terms of Big-O notation, because I still have trouble with Big O.

For another question: $2^{(\log_2 n)} = O(2^{(\log_3 n)})$

I simplfied this to $2^{(\log_2 n)}\over 2^{(\log_3 n)}$ to $n\over n 2^{\log_3 2}$ to $1 \over 2^{\log_3 2)}$ but I'm not sure that I did that correctly when I simplified it down.

And for this question

True or False: $(\log_2 n)^2$ is $O(\log_3 n)^2$

I'm not even sure how I would begin this problem, any hints?

One last quick question about sum of series for the series $S(n) = 1^c + 2^c + 3^c + \cdots + n^c$

I get $\sum_{i=1}^n i^c$ Does that equal the equation $n^{c+1} -1 \over n-1$?

share|improve this question
1  
Forget about $n=1$, the (not so good) definition has problems there. One log is a constant multiple of another. So the big O relationship trivially holds. –  André Nicolas Oct 3 '12 at 4:06
add comment

1 Answer 1

$$ \log_2 n = \frac{\log_3 n}{\log_3 2} = c\log_3 n\text{ where } c = \frac{1}{\log_3 2}=\log_2 3. $$ If $\log_2 n = c\log_3 n$ then $\log_2 n\le c\log_3 n$. If $\log_2 n\le c\log_3 n$ then $\log_2 n = O(\log_3 n)$.

(A crucial point here is that the quantity called "$c$" does not depend on $n$. "Constant" always means "not depending on something". What "something" is depends on the context.)

share|improve this answer
    
I'm not sure how showing c = $1\over log_3 2$ $= log_2 3$ fits into showing that it is $O(log_3 n)$. Is it just showing that in this context that is what c is? And if that is the value of c the inequalities follow and that it is $O(log_3 n)$? Or well actually they would be equal in this situation correct? not less than, and is that why the answer is true? –  Kevin Oct 3 '12 at 4:28
    
The constant is either $1/\log_3 2$ or $\log_2 3$; it's the same number either way. –  Michael Hardy Oct 3 '12 at 4:47
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.