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$?

  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Oct 3 '12 at 4:06

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

  • $\begingroup$ 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? $\endgroup$ – Kevin Oct 3 '12 at 4:28
  • $\begingroup$ The constant is either $1/\log_3 2$ or $\log_2 3$; it's the same number either way. $\endgroup$ – Michael Hardy Oct 3 '12 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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