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